Raise a Matrix to Arbitrary Power

Question

I have a $k\times k$ matrix $$ A_{k}= \begin{pmatrix} 1 & 1 & \cdots & 1 & 1 & 1 \\ 1 & 1 & \cdots & 1 &1 & 0\\ &\vdots & &\vdots \\ 1 & 1 & \cdots & 0 & 0 & 0\\ 1 & 0 & \cdots & 0 & 0 & 0 \end{pmatrix} $$ where $k\ge 2$. I would like to raise this matrix to arbitrary power $n$. Does anyone have any idea on how to proceed?

The only method I know is to convert the matrix in diagonal form, i.e. find the eigenvectors. However, I don't think that this method works here, because $k$ is arbitrary. In addition, as long as $k\ge 3$, the eigenvalues are extremely complicated.

I would appreciate it if anyone can suggest some ideas!

In addition, it would be also helpful if you can provide some idea in calculating $A_{k}^{n}$, even for some small $n$ (preferably large than $5$).

Thank you every much!

Answer 1

A result can be obtained by direct computation. It can be seen that the first row of $A_k$ is $$(A_k)_{1, j} = 1.$$ Then, the first row of $A_k^{\nu+1}$ is produced by taking partial sums as follows $$(A_k^{\nu+1})_{1, j} = \sum_{i=j}^{k}(A_k^\nu)_{1, i}.$$ As an example, take $A_6$. The first row of $A_5$ is $$(A_{5})_{1:} = \begin{bmatrix}1 & 1 & 1 & 1&1\end{bmatrix}.$$ Then $$\begin{aligned}(A_{5}^2)_{1:} ={}& \begin{bmatrix}1+1+1+1+1 & 1+1+1+1 & \cdots & 1+1 & 1\end{bmatrix} \\ {}={}& \begin{bmatrix}5 & 4 & 3 & 2 & 1\end{bmatrix}. \end{aligned}$$ and, $$\begin{aligned}(A_{5}^3)_{1:} ={}& \begin{bmatrix}5+4+3+2+1 & 5+4+3+2 & \cdots & 5+4 & 5\end{bmatrix} \\ {}={}& \begin{bmatrix} 15 & 14 & 12 & 9 & 5\end{bmatrix}. \end{aligned}$$ and, likewise, $$\begin{aligned}(A_{5}^4)_{1:} ={}& \begin{bmatrix}15+15+12+9+5 & \ldots & 15+14 & 15\end{bmatrix} \\ {}={}& \begin{bmatrix} 55 & 50 & 41 & 29 & 15\end{bmatrix}. \end{aligned}$$

For $A_5$, the elements of the first row are the elements of the 5-wave sequence, aka A038201.

Similarly, we can obtain the remaining elements of $A_{k}^\nu$. Note also that $A_2^\nu = F_{\nu+1}$ (the $\nu$-th Fibonacci number).

Note also that the first column is the transpose of the first row, that is $(A_k^{\nu})_{1,i} = (A_{k}^{\nu})_{i, 1}$, and the same happens on the submatrices $(A_{k}^{\nu})_{i:k, i:k}$ for $i=2,\ldots, k$.

One more observation is that for $\nu\geq 2$ $$ (A_{k}^{\nu})_{i+1,k}=(A_{k}^{\nu})_{1,k-i} - (A_{k}^{\nu})_{1,k-i+1}, $$ for $i=1,\ldots, k-1$. As an example, take $A_5^4$; it is $$ A_5^4 = \begin{bmatrix} 55 & 50 & 41 & 29 & 15 \\ 50 & * & * & * & 29-15 \\ 41 & * & * & * & 41-29 \\ 29& * & * & * & 50-41 \\ 15& * & * & * & 55-50 \end{bmatrix} {}={} \begin{bmatrix} 55 & 50 & 41 & 29 & 15 \\ 50 & * & * & * & 14 \\ 41 & * & * & * & 12 \\ 29& * & * & * & 9 \\ 15& * & * & * & 5 \end{bmatrix}, $$ and by exploiting the aforementioned symmetry of $A_k^\nu$ we can fill in the last row too $$ A_5^4 {}={} \begin{bmatrix} 55 & 50 & 41 & 29 & 15 \\ 50 & * & * & * & 14 \\ 41 & * & * & * & 12 \\ 29& * & * & * & 9 \\ 15& 14 & 12 & 9 & 5 \end{bmatrix}. $$

The second row can be computed directly by taking partial sums. However, having computed the above elements we can observe that $$(A_k^\nu)_{2, k-i} = (A_k^\nu)_{2, k-i-1} - (A_k^\nu)_{2, k-i} + (A_k^\nu)_{2, k-i+1},$$ for $\nu\geq 2$ and $i=1,\ldots, k-1$.

Going back to the above example, $$\begin{aligned} A_5^4 {}={}& \begin{bmatrix} 55 & 50 & 41 & 29 & 15 \\ 50 & 55-50+41 & 50-41+29 & 41-29+15 & 14 \\ 41 & * & * & * & 12 \\ 29& * & * & * & 9 \\ 15& 14 & 12 & 9 & 5 \end{bmatrix} \\ {}={}& \begin{bmatrix} 55 & 50 & 41 & 29 & 15 \\ 50 & 46 & 38 & 27 & 14 \\ 41 & * & * & * & 12 \\ 29& * & * & * & 9 \\ 15& 14 & 12 & 9 & 5 \end{bmatrix} \end{aligned}$$ and because of the symmetry of $A_5^4$ we can fill in some more elements as follows: $$ A_5^4 {}={} \begin{bmatrix} 55 & 50 & 41 & 29 & 15 \\ 50 & 46 & 38 & 27 & 14 \\ 41 & 38 & * & * & 12 \\ 29& 27 & * & * & 9 \\ 15& 14 & 12 & 9 & 5 \end{bmatrix} $$

---

Algorithm

Here is an algorithm to construct $A_k^\nu$.

Step 0. Construct the first row/column; here is a little MATLAB script:

function v = first_row_power_ak(k, nu)
v = ones(1, k);
z = ones(1, k);
for j=1:nu-1
    for i=1:k
        z(i) = sum(v(1:end-i+1));
    end
    v = z;
end

Take as an example $k=7$ and $\nu=5$; the first column is $(658, 630, 575, 495, 393, 273, 140)$. This means, that the matrix is $$ A_k^\nu = \begin{bmatrix} 658&630&575&495&393&273&140\\ 630& *& *& *& *& *& *\\ 575& *& *& *& *& *& *\\ 495& *& *& *& *& *& *\\ 393& *& *& *& *& *& *\\ 273& *& *& *& *& *& *\\ 140& *& *& *& *& *& * \end{bmatrix} $$

Step 1. Place the cursor at $k-1$ and follow a vertical direction of completion (the meaning of this will become clear in a moment). Fill in the missing elements in the last column with successive differences of the elements of the first row; then fill in the elements of the last row (they are the same elements):

$$A_k^\nu = \begin{bmatrix} 658& 630& 575& 495& 393& {\color{red}{273}}& 140\\ 630& *& *& *& *& *& {\color{blue}{133}}\\ 575& *& *& *& *& *& \color{blue}{120}\\ 495& *& *& *& *& *& \color{blue}{102}\\ 393& *& *& *& *& *& \color{blue}{80}\\ 273& *& *& *& *& *& \color{blue}{55}\\ 140& \color{gray}{133}& \color{gray}{120}& \color{gray}{102}& \color{gray}{80}& \color{gray}{55}& \color{blue}{28} \end{bmatrix}$$

For example, $133 = 273 - 140$ and $120 = 393-273$.

Step 2. Place the cursor at $k-2$ and follow a horizontal direction of completion. Hereafter we will be using alternating directions of completion. We fill in the missing elements of the second row by taking differences between the first row (starting at the cursor) and the last column (which we filled in previously).

$$A_k^\nu = \begin{bmatrix} 658& 630& 575& 495& {\color{red}{393}}& 273& 140\\ 630& {\color{blue}{603}}& {\color{blue}{550}}& {\color{blue}{473}}& {\color{blue}{375}}& {\color{blue}{260}}& \color{green}{133}\\ 575& {\color{gray}{550}}& *& *& *& *& \color{green}{120}\\ 495& {\color{gray}{473}}& *& *& *& *& \color{green}{102}\\ 393& {\color{gray}{375}}& *& *& *& *& \color{green}{80}\\ 273& {\color{gray}{260}}& *& *& *& *& \color{green}{55}\\ 140& 133& 120& 102& 80& 55& 28 \end{bmatrix}$$

For example, $260=393-133$, $375=495-120$ and so on.

NOTE: The green numbers were computed in the previous step. Essentially, we're doing blue = red - green.

Step 3. Move the curson to $k-3$ and follow a vertical direction of completion: now we will fill in the missing elements of the 6th column. We have

$$A_k^\nu = \begin{bmatrix} 658& 630& 575& {\color{red}{495}}& 393& 273& 140\\ 630& 603& \color{green}{550}& \color{green}{473}& \color{green}{375}& \color{green}{260}& 133\\ 575& 550& *& *& *& {\color{blue}{235}}& 120\\ 495& 473& *& *& *& {\color{blue}{200}}& 102\\ 393& 375& *& *& *& {\color{blue}{157}}& 80\\ 273& 260& {\color{gray}{235}}& {\color{gray}{200}}& {\color{gray}{157}}& {\color{blue}{108}}& 55\\ 140& 133& 120& 102& 80& 55& 28 \end{bmatrix}$$

Here $235=495-260$, $200=575-375$ and so on.

Step 4. Move the cursor to $k-4$ and follow a horizontal direction of completion to fill in the missing elements of the third column

$$A_k^\nu = \begin{bmatrix} 658& 630& {\color{red}{575}}& 495& 393& 273& 140\\ 630& 603& 550& 473& 375& 260& 133\\ 575& 550& {\color{blue}{501}}& {\color{blue}{430}}& {\color{blue}{340}}& \color{green}{235}& 120\\ 495& 473& {\color{gray}{430}}& *& *& \color{green}{200}& 102\\ 393& 375& {\color{gray}{340}}& *& *& \color{green}{157}& 80\\ 273& 260& 235& 200& 157& 108& 55\\ 140& 133& 120& 102& 80& 55& 28 \end{bmatrix}$$ where $340=575-235$, $430 = 630-200$, and $501 = 658-157$.

Step 5. We move the cursor to the left (to position $2$) and change again to a vertical direction of completion. $$A_k^\nu = \begin{bmatrix} 658& {\color{red}{630}}& 575& 495& 393& 273& 140\\ 630& 603& 550& 473& 375& 260& 133\\ 575& 550& 501& \color{green}{430}& \color{green}{340}& 235& 120\\ 495& 473& 430& *& {\color{blue}{290}}& 200& 102\\ 393& 375& 340& {\color{gray}{290}}& {\color{blue}{228}}& 157& 80\\ 273& 260& 235& 200& 157& 108& 55\\ 140& 133& 120& 102& 80& 55& 28 \end{bmatrix}$$ where $290=630-340$ and $228 = 658-430$.

I will leave the last step to you.

This algorithm can be applied to determine any matrix of the type $A_k^\nu$

---

MATLAB script

Here is a MATLAB script to compute $A_k^\nu$:

function x = antitri_k_nu(k, nu)
x = zeros(k, k);
a = first_row_power_ak(k, nu);
x(1, :) = a;

idx_r = 1;
idx_c = k;
dir = 0; % 0 = row, 1 = col
for j=k-1:-1:1
    lhs = x(1, 1:j);
    if dir ==0
        rhs = x(idx_r, idx_c:-1:idx_c-j+1);
        idx_r = idx_r + 1;        
    else
        rhs = x(idx_r:idx_r+j-1, idx_c);
        idx_c = idx_c - 1;
    end
    u = flipud(lhs(:)) - rhs(:);
    dir = ~dir;
    if dir==0
      x(idx_r, idx_c:-1:idx_c-length(u)+1) = u;
    else
      x(idx_r:idx_r+length(u)-1, idx_c) = u;
    end
end

for i=2:k
    for j=1:i
        x(i,j) = x(j,i);
    end
end