On the Additive Complexity of GCD and LCM Matrices

In the paper, the additive complexity of matrices formed by positive integer powers of greatest common divisors and least common multiples of the indices of the rows and columns is considered. It is proved that the complexity of the $n\times n$ matrix formed by the numbers $\text{GCD}^r(i,k)$ over the basis $\{x+y\}$ is asymptotically equal to $rn \log_2 n$ as $n\to\infty$, and the complexity of the $n\times n$ matrix formed by the numbers $\text{LCM}^r(i,k)$ over the basis $\{x+y,-x\}$ is asymptotically equal to $2rn \log_2 n$ as $n\to \infty$.