We have the given matrix
A = [ 1 1 1 0 1 1 0 0 1 ] . A=\begin{bmatrix}1&1&1\\0&1&1\\0&0&1\end{bmatrix}. A = 1 0 0 1 1 0 1 1 1 .
First we separate the diagonal (identity) part from the strictly upper-triangular part. Writing I I I for the identity matrix, we observe
A = I + U , where U = A − I = [ 0 1 1 0 0 1 0 0 0 ] . A=I+U,\qquad\text{where}\qquad
U=A-I=\begin{bmatrix}0&1&1\\0&0&1\\0&0&0\end{bmatrix}. A = I + U , where U = A − I = 0 0 0 1 0 0 1 1 0 .
Because every entry of U U U that lies on or below the main diagonal is zero, U U U is nilpotent. Let us check the powers of U U U explicitly:
U 2 = [ 0 1 1 0 0 1 0 0 0 ] [ 0 1 1 0 0 1 0 0 0 ] = [ 0 ⋅ 0 + 1 ⋅ 0 + 1 ⋅ 0 0 ⋅ 1 + 1 ⋅ 0 + 1 ⋅ 0 0 ⋅ 1 + 1 ⋅ 1 + 1 ⋅ 0 0 0 0 0 0 0 ] = [ 0 0 1 0 0 0 0 0 0 ] , U^2
=\begin{bmatrix}0&1&1\\0&0&1\\0&0&0\end{bmatrix}
\begin{bmatrix}0&1&1\\0&0&1\\0&0&0\end{bmatrix}
=\begin{bmatrix}0\cdot0+1\cdot0+1\cdot0 & 0\cdot1+1\cdot0+1\cdot0 & 0\cdot1+1\cdot1+1\cdot0\\
0&0&0\\
0&0&0
\end{bmatrix}
=\begin{bmatrix}0&0&1\\0&0&0\\0&0&0\end{bmatrix}, U 2 = 0 0 0 1 0 0 1 1 0 0 0 0 1 0 0 1 1 0 = 0 ⋅ 0 + 1 ⋅ 0 + 1 ⋅ 0 0 0 0 ⋅ 1 + 1 ⋅ 0 + 1 ⋅ 0 0 0 0 ⋅ 1 + 1 ⋅ 1 + 1 ⋅ 0 0 0 = 0 0 0 0 0 0 1 0 0 ,
and
U 3 = U 2 U = [ 0 0 1 0 0 0 0 0 0 ] [ 0 1 1 0 0 1 0 0 0 ] = [ 0 0 0 0 0 0 0 0 0 ] = 0. U^3
=U^2U
=\begin{bmatrix}0&0&1\\0&0&0\\0&0&0\end{bmatrix}
\begin{bmatrix}0&1&1\\0&0&1\\0&0&0\end{bmatrix}
=\begin{bmatrix}0&0&0\\0&0&0\\0&0&0\end{bmatrix}=0. U 3 = U 2 U = 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 1 1 0 = 0 0 0 0 0 0 0 0 0 = 0.
Thus U 3 = 0 , U^3=0, U 3 = 0 , so U U U has nilpotency index 3 3 3 .
For any positive integer n n n we need A n = ( I + U ) n . A^n=(I+U)^n. A n = ( I + U ) n .
Because I I I commutes with U , U, U , the usual binomial theorem for commuting matrices applies:
( I + U ) n = ∑ k = 0 n ( n k ) I n − k U k = I + ( n 1 ) U + ( n 2 ) U 2 + ( n 3 ) U 3 . (I+U)^n
=\sum_{k=0}^{n}\binom{n}{k}I^{\,n-k}U^{\,k}
=I+\binom{n}{1}U+\binom{n}{2}U^{2}+\binom{n}{3}U^{3}. ( I + U ) n = ∑ k = 0 n ( k n ) I n − k U k = I + ( 1 n ) U + ( 2 n ) U 2 + ( 3 n ) U 3 .
Since U 3 = 0 , U^{3}=0, U 3 = 0 , all terms with k ≥ 3 k\ge 3 k ≥ 3 vanish. Therefore
A n = I + n U + n ( n − 1 ) 2 U 2 . A^n=I+nU+\frac{n(n-1)}{2}\,U^{2}. A n = I + n U + 2 n ( n − 1 ) U 2 .
Now we form the required matrix
M = A + A 2 + A 3 + ⋯ + A 20 = ∑ n = 1 20 A n . M=A+A^{2}+A^{3}+\dots+A^{20}=\sum_{n=1}^{20}A^{n}. M = A + A 2 + A 3 + ⋯ + A 20 = ∑ n = 1 20 A n .
Substituting the above expression for A n A^n A n we obtain
M = ∑ n = 1 20 ( I + n U + n ( n − 1 ) 2 U 2 ) = ( ∑ n = 1 20 I ) + ( ∑ n = 1 20 n ) U + ( ∑ n = 1 20 n ( n − 1 ) 2 ) U 2 . M=\sum_{n=1}^{20}\Bigl(I+nU+\frac{n(n-1)}{2}U^{2}\Bigr)
=\Bigl(\sum_{n=1}^{20}I\Bigr)
+\Bigl(\sum_{n=1}^{20}n\Bigr)U
+\Bigl(\sum_{n=1}^{20}\frac{n(n-1)}{2}\Bigr)U^{2}. M = ∑ n = 1 20 ( I + n U + 2 n ( n − 1 ) U 2 ) = ( ∑ n = 1 20 I ) + ( ∑ n = 1 20 n ) U + ( ∑ n = 1 20 2 n ( n − 1 ) ) U 2 .
Let us evaluate each scalar sum one by one.
The first sum is simply
∑ n = 1 20 I = 20 I . \sum_{n=1}^{20}I = 20I. ∑ n = 1 20 I = 20 I .
For the second sum we use the formula for the sum of the first N N N natural numbers, 1 + 2 + ⋯ + N = N ( N + 1 ) 2 , 1+2+\dots+N=\dfrac{N(N+1)}{2}, 1 + 2 + ⋯ + N = 2 N ( N + 1 ) , with N = 20 N=20 N = 20 :
∑ n = 1 20 n = 20 ⋅ 21 2 = 210. \sum_{n=1}^{20}n=\frac{20\cdot21}{2}=210. ∑ n = 1 20 n = 2 20 ⋅ 21 = 210.
For the third sum we need
∑ n = 1 20 n ( n − 1 ) 2 = 1 2 ∑ n = 1 20 ( n 2 − n ) . \sum_{n=1}^{20}\frac{n(n-1)}{2}
=\frac12\sum_{n=1}^{20}(n^{2}-n). ∑ n = 1 20 2 n ( n − 1 ) = 2 1 ∑ n = 1 20 ( n 2 − n ) .
We compute the two parts separately.
The formula for the sum of squares is 1 2 + 2 2 + ⋯ + N 2 = N ( N + 1 ) ( 2 N + 1 ) 6 . 1^{2}+2^{2}+\dots+N^{2}=\dfrac{N(N+1)(2N+1)}{6}. 1 2 + 2 2 + ⋯ + N 2 = 6 N ( N + 1 ) ( 2 N + 1 ) . Putting N = 20 N=20 N = 20 we get
∑ n = 1 20 n 2 = 20 ⋅ 21 ⋅ 41 6 = 2870. \sum_{n=1}^{20}n^{2}=\frac{20\cdot21\cdot41}{6}=2870. ∑ n = 1 20 n 2 = 6 20 ⋅ 21 ⋅ 41 = 2870.
We already know ∑ n = 1 20 n = 210. \sum_{n=1}^{20}n=210. ∑ n = 1 20 n = 210. Therefore
∑ n = 1 20 ( n 2 − n ) = 2870 − 210 = 2660 , \sum_{n=1}^{20}(n^{2}-n)=2870-210=2660, ∑ n = 1 20 ( n 2 − n ) = 2870 − 210 = 2660 ,
and hence
∑ n = 1 20 n ( n − 1 ) 2 = 2660 2 = 1330. \sum_{n=1}^{20}\frac{n(n-1)}{2}=\frac{2660}{2}=1330. ∑ n = 1 20 2 n ( n − 1 ) = 2 2660 = 1330.
Putting these scalar sums back, we have
M = 20 I + 210 U + 1330 U 2 . M=20I+210\,U+1330\,U^{2}. M = 20 I + 210 U + 1330 U 2 .
To get the required answer, we must add all the entries of M M M . Because summation of matrix elements is a linear operation, we can add the totals contributed by I , U I,\;U I , U and U 2 U^{2} U 2 separately.
The sum of the elements of the identity matrix is clearly
Sum ( I ) = 1 + 1 + 1 = 3. \text{Sum}(I)=1+1+1=3. Sum ( I ) = 1 + 1 + 1 = 3.
The matrix U U U is
U = [ 0 1 1 0 0 1 0 0 0 ] , U=\begin{bmatrix}0&1&1\\0&0&1\\0&0&0\end{bmatrix}, U = 0 0 0 1 0 0 1 1 0 ,
so
Sum ( U ) = 0 + 1 + 1 + 0 + 0 + 1 + 0 + 0 + 0 = 3. \text{Sum}(U)=0+1+1+0+0+1+0+0+0=3. Sum ( U ) = 0 + 1 + 1 + 0 + 0 + 1 + 0 + 0 + 0 = 3.
The matrix U 2 U^{2} U 2 is
U 2 = [ 0 0 1 0 0 0 0 0 0 ] , U^{2}=\begin{bmatrix}0&0&1\\0&0&0\\0&0&0\end{bmatrix}, U 2 = 0 0 0 0 0 0 1 0 0 ,
thus
Sum ( U 2 ) = 0 + 0 + 1 + 0 + 0 + 0 + 0 + 0 + 0 = 1. \text{Sum}(U^{2})=0+0+1+0+0+0+0+0+0=1. Sum ( U 2 ) = 0 + 0 + 1 + 0 + 0 + 0 + 0 + 0 + 0 = 1.
Consequently, the total sum of all elements of M M M equals
Sum ( M ) = 20 ⋅ Sum ( I ) + 210 ⋅ Sum ( U ) + 1330 ⋅ Sum ( U 2 ) = 20 ⋅ 3 + 210 ⋅ 3 + 1330 ⋅ 1 = 60 + 630 + 1330 = 2020. \begin{aligned}
\text{Sum}(M)
&=20\cdot\text{Sum}(I)+210\cdot\text{Sum}(U)+1330\cdot\text{Sum}(U^{2})\\
&=20\cdot3+210\cdot3+1330\cdot1\\
&=60+630+1330\\
&=2020.
\end{aligned} Sum ( M ) = 20 ⋅ Sum ( I ) + 210 ⋅ Sum ( U ) + 1330 ⋅ Sum ( U 2 ) = 20 ⋅ 3 + 210 ⋅ 3 + 1330 ⋅ 1 = 60 + 630 + 1330 = 2020.
So, the answer is 2020 2020 2020 .