In this section we give the walk polynomial of the complete bipartite, star, wheel, and gear graphs.
Proof
Since the diameter of Sn is 2, we need only two matrices, the adjacency matrix A and its square matrix A2, each of order n × n:
$$\begin{array}{}
\displaystyle
A=\left(
\begin{array}{cc}
O_{1,1} & J_{1,n-1} \\
J_{1,n-1}^{T} & O_{n-1,n-1} \\
\end{array}
\right),
\end{array}$$
where O and J are matrices of zeros and ones, respectively. You can see the adjacency matrix of S7:
$$\begin{array}{}
\displaystyle
A=\left(
\begin{array}{ccccccc}
0 & 1 & 1 & 1 & 1 & 1 & 1 \\
1 & 0 & 0 & 0 & 0 & 0 & 0 \\
1 & 0 & 0 & 0 & 0 & 0 & 0 \\
1 & 0 & 0 & 0 & 0 & 0 & 0 \\
1 & 0 & 0 & 0 & 0 & 0 & 0 \\
1 & 0 & 0 & 0 & 0 & 0 & 0 \\
1 & 0 & 0 & 0 & 0 & 0 & 0 \\
\end{array}
\right)
\end{array}$$
Since the upper triangular part of the adjacency matrix A is the matrix J1,n–1, the sum of entries of this matrix is n–1. Thus the number of all walks of length 1 in J1,n–1 is w1 = n–1. Similarly, the general form of A2 is
$$\begin{array}{}
\displaystyle
A^{2}=\left(
\begin{array}{cc}
(n-1)J_{1,1} & O_{1,n-1} \\
O_{1,n-1}^{T} & J_{n-1,n-1} \\
\end{array}
\right),
\end{array}$$
where n(J1,1) represents the multiplication of J1,1 with the number n–1. The following is the second power of the adjacency matrix of S7.
$$\begin{array}{}
\displaystyle
A^2=\left(
\begin{array}{ccccccc}
6 & 0 & 0 & 0 & 0 & 0 & 0 \\
0 & 1 & 1 & 1 & 1 & 1 & 1 \\
0 & 1 & 1 & 1 & 1 & 1 & 1 \\
0 & 1 & 1 & 1 & 1 & 1 & 1 \\
0 & 1 & 1 & 1 & 1 & 1 & 1 \\
0 & 1 & 1 & 1 & 1 & 1 & 1 \\
0 & 1 & 1 & 1 & 1 & 1 & 1 \\
\end{array}
\right)
\end{array}$$
Note that the walks of length 2 the contribution comes only from the matric Jn–1,n–1, and in this case the sum of all entries of this matrix is (n–1)2. Now the number of walks of length 2 in Sn is
$$\begin{array}{}
\displaystyle
w_{2} &=& \frac{1}{2}[\,\mbox{the sum of entries of}\,\, J_{n-1,n-1}-tr(J_{n-1,n-1})] \\
\displaystyle
&=& \frac{1}{2}[(n-1)^{2}-(n-1)] \\
\displaystyle
&=& \frac{1}{2}[n^{2}-3n+2],
\end{array}$$
and the proof is finished.
Proof
Here, again, the diameter of the wheel graph is 2. So, again, we need just two matrices, the adjacency matrix A and its square A2. The adjacency matrix corresponding to Wn is A = (aij), where
$$\begin{array}{}
\displaystyle
a_{ij}=\left\{ \begin{array}{lll}
0,& i=j \\
1,& i=1 \,\,\mbox{or}\,\, j=1 \\
1,&j=i+1 \,\,\mbox{or}\,\, i=j+1 \\
1,&i=2,j=n \,\,\mbox{and}\,\, i=n,j=2 \\
0,&\mbox{otherwise}. \\
\end{array} \right.
\end{array}$$
For better understanding, please the following adjacency matrix of W7.
$$\begin{array}{}
\displaystyle
A=\left(
\begin{array}{ccccccc}
0 & 1 & 1 & 1 & 1 & 1 & 1 \\
1 & 0 & 1 & 0 & 0 & 0 & 1 \\
1 & 1 & 0 & 1 & 0 & 0 & 0 \\
1 & 0 & 1 & 0 & 1 & 0 & 0 \\
1 & 0 & 0 & 1 & 0 & 1 & 0 \\
1 & 0 & 0 & 0 & 1 & 0 & 1 \\
1 & 1 & 0 & 0 & 0 & 1 & 0 \\
\end{array}
\right)
\end{array}$$
You can see that there are three types of entries where nonzero entries appear; the nonzero entries are actually 1s. The first type of entries appear at positions where either i = 1 or j = 1, and their count is 2(n–1); The second type of entries appear at positions where either i = j + 1 or j = 1 + 1, and their count is 2((n–1)–1); The third type of entries appear at positions where either i = 2, j = n or i = n, j = 2, and their count is 2. You may observe that all the entries of main diagonal are 0. So, the number of all distinct walks of length 1 in Wn is
$\begin{array}{}
\displaystyle
w_{1}=\frac{1}{2}(2(n-1))+2((n-1)-1))+2=2(n-1).
\end{array}$
The upper triangular entries of A2 = (bij) are
$$\begin{array}{}
\displaystyle
b_{ij}=\left\{ \begin{array}{lll}
1,& j=i+1,i=2,\ldots,n-1 \\
1,& i=2,j=n \\
2,& j=i+2,i=2,\ldots,n-2 \\
2,& i=2,j=n-1 \\
2,& i=3,j=n-1 \\
2,& i=1,j=2,\ldots,n \\
1,& j=i+3,\ldots,i+(n-4), 2\leq i \leq n-3, i+n-4\leq n \\
\end{array} \right.
\end{array}$$
The following is A2 of W7.
$$\begin{array}{}
\displaystyle
A^2=\left(
\begin{array}{ccccccc}
6 & 2 & 2 & 2 & 2 & 2 & 2 \\
2 & 3 & 1 & 2 & 1 & 2 & 1 \\
2 & 1 & 3 & 1 & 2 & 1 & 2 \\
2 & 2 & 1 & 3 & 1 & 2 & 1 \\
2 & 1 & 2 & 1 & 3 & 1 & 2 \\
2 & 2 & 1 & 2 & 1 & 3 & 1 \\
2 & 1 & 2 & 1 & 2 & 1 & 3 \\
\end{array}
\right)
\end{array}$$
Now we give the sum of all the entries: and the first type of entries are all 1s and appear at the positions where j = i + 1, and their count is (n–2). The second type of entries are all 1s and appear at the positions where i = 2, j = n, and their count is 1. The third type of entries are all 2s and appear at the positions where j = i + 2, i = 2 and their count is (n–3); The fourth type of entries are all 2s and appear at the positions wherei = 2, j = n–1, and their count is 1; the fifth type of entries are all 2s and appear at the positions where i = 3, j = n–1, and their count is 1; the sixth type of entry is are all 2s and appear at the positions where i = 1, j = 2, …, n, and their count is (n–1); the seventh type of entries are all 1s and appear at the positions where j = i + 3, …, i + (n–4), 2 ≤ i ≤ n–3, i + n–4 ≤ n, and their count is
$\begin{array}{}
\sum_{4}^{n-3}(n-i).
\end{array}$. You may observe that all the entries are of upper triangular entries. So, the number of all distinct walks of length 2 in Wn is
$\begin{array}{}
w_{2}=((n-2)+1+(n-3)+1+1+(n-1)+\sum_{4}^{n-3}(n-i))=\frac{1}{2}(n^2+3n-4)
\end{array}$
Proof
Since the diameter of the gear graph is 4, we need four matrices, A, A2, A3, and A4.
Walks of lengths 1: Since only the upper-triangular entries contribute towards the walk polynomial, we give only the nonzero upper-triangular entries of the (2n + 1) × (2n + 1) adjacency matrix A = (aij) of Gn:
$$\begin{array}{}
\displaystyle
a_{ij}=\left\{ \begin{array}{lll}
1,& i=1,\ldots,2n-1, j=i+1 \\
1,& i=1,j=2n \\
1,& i=odd, i\lt2n+1,j=2n+1 \\
0,&\mbox{otherwise}. \\
\end{array} \right.
\end{array}$$
Let us have a look at the adjacency matrix of G7:
$$\begin{array}{}
\displaystyle
A=\left(
\begin{array}{ccccccccccccccc}
0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 \\
1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\
0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\
0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\
0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\
0 & 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\
0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 1 \\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 1 \\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 \\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 1 & 1 \\
1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\
1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 0 \\
\end{array}
\right)
\end{array}$$
You can see that there are three types of entries where nonzero entries appear; the nonzero entries are actually 1s. The first type of entries appear at positions where i = 1, …, 2n–1 and j = i + 1, and so their count is 2n–1; the second type of entries appear at positions where i = 1 and j = 2n, and so their count is 1; the third type of entries appear at positions where i is odd and is less than 2n + 1 and j = 2n + 1, and so their count is n. So, the number of all distinct walks of length 1 in Gn is w1 = ((2n–1) + 1 + n) = (3n).
Walks of lengths 2: Now we find walks of lengths 2. The upper triangular entries of A2 = (bij) are
$$\begin{array}{}
\displaystyle
b_{ij}=\left\{ \begin{array}{lll}
2,& i=odd,1\leq i\leq (2n-3),j=i+2 \\
1,& i=even,2\leq i\leq (2n-2),j=i+2 \\
2,& i=even,2\leq i\leq (2n),j=2n+1 \\
1,& i=odd,1\leq i\leq (2n-5),j=i+4 \\
1,& i=odd,1\leq i\leq (2n-7),j=i+6 \\
1,& i=odd,1\leq i\leq 3,j=i+8 \\
2,& i=1,j=2n-1 \\
1,& i=2,j=2n \\
\end{array} \right.
\end{array}$$
For better understanding you may have a look at the walks of lengths 2 in the matrix A2 of G7.
$$\begin{array}{}
\displaystyle
A^{2}=\left(
\begin{array}{ccccccccccccccc}
3 & 0 & 2 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 2 & 0 & 0 \\
0 & 2 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 2 \\
2 & 0 & 3 & 0 & 2 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 0 \\
0 & 1 & 0 & 2 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 2 \\
1 & 0 & 2 & 0 & 3 & 0 & 2 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 0 \\
0 & 0 & 0 & 1 & 0 & 2 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 2 \\
1 & 0 & 1 & 0 & 2 & 0 & 3 & 0 & 2 & 0 & 1 & 0 & 1 & 0 & 0 \\
0 & 0 & 0 & 0 & 0 & 1 & 0 & 2 & 0 & 1 & 0 & 0 & 0 & 0 & 2 \\
1 & 0 & 1 & 0 & 1 & 0 & 2 & 0 & 3 & 0 & 2 & 0 & 1 & 0 & 0 \\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 2 & 0 & 1 & 0 & 0 & 2 \\
1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 2 & 0 & 3 & 0 & 2 & 0 & 0 \\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 2 & 0 & 1 & 2 \\
2 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 2 & 0 & 3 & 0 & 0 \\
0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 2 & 2 \\
0 & 2 & 0 & 2 & 0 & 2 & 0 & 2 & 0 & 2 & 0 & 2 & 0 & 2 & 7 \\
\end{array}
\right)
\end{array}$$
Now we give the sum of all these entries. The first type of entries are all 2s and appear at positions where i is odd and 1 ≤ i ≤ (2n–3), j = i + 2, and their count is (n–1). the second type of entries are all 1s and appear at positions where i is even and 2 ≤ i ≤ (2n–2) and j = i + 2, and their count is (n–1); the third type of entries are all 2s and appear at positions where i is even and 2 ≤ i ≤ (2n) and j = 2n + 1, and their count is n; the fourth type of entries are all 1s and appear at positions where i is odd and 1 ≤ i ≤ (2n–5) and j = i + 4, and their count is n–2; the fifth type of entry is are all 1s and appear at positions where i is odd and 1 ≤ i ≤ (2n–7) and j = i + 6, and their count is (n–3); the sixth type of entries are all 1s and appear at positions where i is odd and 1 ≤ i ≤ 3 and j = i + 8, and their count is (n–4); the seventh type of entries are all 2s and appear at positions where i = 1, j = 2n–1, and their count is 1. The eighth type of entries are all 1s and appear at positions where i = 2, j = 2n, and their count is 1. So, the number of all distinct walks of length 2 is
$\begin{array}{}
\displaystyle
w_{2}=\frac{n^2+7n}{2}.
\end{array}$
Walks of lengths 3: In order to find walks of length 3, we need upper triangular entries of the matrix A3:
$$\begin{array}{}
\displaystyle
c_{ij}=\left\{ \begin{array}{lll}
5,& 1\leq i\leq (2n-1),j=i+1 \\
3,& 1\leq i\leq 3,j=i+(2n-3) \\
3,& 1\leq i\leq 2n-3,j=i+3\\
2,& 1\leq i\leq 2n-5,j=i+5 \\
2,& 1\leq i\leq 2n-7,,j=i+7 \\
5,& i=1,j=n-1 \\
n+4,& i\,\, \mbox{is odd}, 1\leq i \lt2n+1, j=2n+1 \\
\end{array} \right.
\end{array}$$
The following is the matrix A3 of G7.
$$\begin{array}{}
\displaystyle
A^3=\left(
\begin{array}{ccccccccccccccc}
0 & 5 & 0 & 3 & 0 & 2 & 0 & 2 & 0 & 2 & 0 & 3 & 0 & 5 & 11 \\
5 & 0 & 5 & 0 & 3 & 0 & 2 & 0 & 2 & 0 & 2 & 0 & 3 & 0 & 0 \\
0 & 5 & 0 & 5 & 0 & 3 & 0 & 2 & 0 & 2 & 0 & 2 & 0 & 3 & 11 \\
3 & 0 & 5 & 0 & 5 & 0 & 3 & 0 & 2 & 0 & 2 & 0 & 2 & 0 & 0 \\
0 & 3 & 0 & 5 & 0 & 5 & 0 & 3 & 0 & 2 & 0 & 2 & 0 & 2 & 11 \\
2 & 0 & 3 & 0 & 5 & 0 & 5 & 0 & 3 & 0 & 2 & 0 & 2 & 0 & 0 \\
0 & 2 & 0 & 3 & 0 & 5 & 0 & 5 & 0 & 3 & 0 & 2 & 0 & 2 & 11 \\
2 & 0 & 2 & 0 & 3 & 0 & 5 & 0 & 5 & 0 & 3 & 0 & 2 & 0 & 0 \\
0 & 2 & 0 & 2 & 0 & 3 & 0 & 5 & 0 & 5 & 0 & 3 & 0 & 2 & 11 \\
2 & 0 & 2 & 0 & 2 & 0 & 3 & 0 & 5 & 0 & 5 & 0 & 3 & 0 & 0 \\
0 & 2 & 0 & 2 & 0 & 2 & 0 & 3 & 0 & 5 & 0 & 5 & 0 & 3 & 11 \\
3 & 0 & 2 & 0 & 2 & 0 & 2 & 0 & 3 & 0 & 5 & 0 & 5 & 0 & 0 \\
0 & 3 & 0 & 2 & 0 & 2 & 0 & 2 & 0 & 3 & 0 & 5 & 0 & 5 & 11 \\
5 & 0 & 3 & 0 & 2 & 0 & 2 & 0 & 2 & 0 & 3 & 0 & 5 & 0 & 0 \\
11 & 0 & 11 & 0 & 11 & 0 & 11 & 0 & 11 & 0 & 11 & 0 & 11 & 0 & 0 \\
\end{array}
\right)
\end{array}$$
Now we give the sum of all entries of above diagonals. The first type of entries are 2s. These entries appear in n–4 secondary diagonals, and the entries appear as follows:
$$\begin{array}{}
\displaystyle
c_{ij}=\left\{ \begin{array}{lll}
2,& 1\leq i\leq 2n-5,j=i+5 \\
2,& 1\leq i\leq 2n-7,j=i+7\\
\vdots & \vdots \\
2,& 1\leq i\leq 5,j=i+(2n-5)
\end{array} \right.
\end{array}$$
Since the number of 2s appearing at these positions is n(n–4), their sum is 2n(n–4).
The second type of entries are 5s. These numbers appear on secondary diagonal with 1 ≤ i ≤ 2n–1 and j = i + 1, and their count is 2n–1. Moreover, one 5 appears at the position where i = 1, j = 2n. Since the total number of 5s is 2n, their sum is 10n.
The third type of entries are 3s. These entries appear only in 2 secondary diagonals, and their positions are:
$$\begin{array}{}
\displaystyle
c_{ij}=\left\{ \begin{array}{lll}
3,& 1\leq i\leq 3,j=i+(2n-3) \\
3,& 1\leq i\leq 2n-3,j=i+3\\
\end{array} \right.
\end{array}$$
Since the total number of 3s is 2n, their sum is 6n.
The fourth type of entries are n + 4s and appear at positions where i is odd and 1 ≤ i < 2n + 1 and j = 2n + 1. Since their count is n, the sum of these numbers is n(n + 4).
Finally, the number of all distinct walks of length 3 in Wn is 2n(n–4) + 10n + 6n + n(n + 4) = 3n(n + 4).
Walks of lengths 4: Now we go for distinct walks of length 4 by giving upper triangular entries of the matrix A4 = (dij). You may observe that these entries will form secondary diagonals, which are divided into three types:
Type I.
$$\begin{array}{}
\displaystyle
d_{ij}=\left\{ \begin{array}{lll}
n+12,& i=odd,1\leq i\leq (2n-3),j=i+2 \\
8,& i=even,2\leq i\leq (2n-2),j=i+2 \\
n+9,& i=odd,1\leq i\leq (2n-5),j=i+4 \\
5,& i=even,2\leq i\leq (2n-4),j=i+4 \\
n+8,& i=odd,1\leq i\leq (2n-7),j=i+6 \\
4,& i=even,2\leq i\leq (2n-6),j=i+6 \\
0,& otherwise \\
\end{array} \right.
\end{array}$$
Type II. The last two nonzero secondary diagonals are:
$$\begin{array}{}
\displaystyle
d_{ij}=\left\{ \begin{array}{lll}
n+12,& i=1,j=2n-1 \\
8,& i=2,j=2n \\
n+9,& i=1,j=2n-3 \\
5,& i=2,j=2n-2 \\
n+9,& i=3,j=2n-1 \\
5,& i=4,j=2n \\
\end{array} \right.
\end{array}$$
Type III. There are n–5 secondary diagonals such that the first entry of each of these diagonals is n + 8. In the following m denotes the number of such diagonals, i.e., 1 ≤ m ≤ n–5.
$$\begin{array}{}
\displaystyle
d_{ij}=\left\{ \begin{array}{lll}
n+8,& i=odd,1\leq i\leq 2(n-m)-5,j=2(m+2)+i \\
4,& i=even,1\leq i\leq 2(n-m-2),j=2(m+2)+i \\
\end{array} \right.
\end{array}$$
The entries which are not covered yet are the entries of the last column of A4:
$$\begin{array}{}
\displaystyle
d_{ij}=\left\{ \begin{array}{lll}
2n+8,& i=even,2\leq i\leq 2n,j=2n+1 \\
\end{array} \right.
\end{array}$$
The following is the matrix A4 of G7.
$$\begin{array}{}
\displaystyle
A^4=\left(
\begin{array}{ccccccccccccccc}
21 & 0 & 19 & 0 & 16 & 0 & 15 & 0 & 15 & 0 & 16 & 0 & 19 & 0 & 0 \\
0 & 10 & 0 & 8 & 0 & 5 & 0 & 4 & 0 & 4 & 0 & 5 & 0 & 8 & 22 \\
19 & 0 & 21 & 0 & 19 & 0 & 16 & 0 & 15 & 0 & 15 & 0 & 16 & 0 & 0 \\
0 & 8 & 0 & 10 & 0 & 8 & 0 & 5 & 0 & 4 & 0 & 4 & 0 & 5 & 22 \\
16 & 0 & 19 & 0 & 21 & 0 & 19 & 0 & 16 & 0 & 15 & 0 & 15 & 0 & 0 \\
0 & 5 & 0 & 8 & 0 & 10 & 0 & 8 & 0 & 5 & 0 & 4 & 0 & 4 & 22 \\
15 & 0 & 16 & 0 & 19 & 0 & 21 & 0 & 19 & 0 & 16 & 0 & 15 & 0 & 0 \\
0 & 4 & 0 & 5 & 0 & 8 & 0 & 10 & 0 & 8 & 0 & 5 & 0 & 4 & 22 \\
15 & 0 & 15 & 0 & 16 & 0 & 19 & 0 & 21 & 0 & 19 & 0 & 16 & 0 & 0 \\
0 & 4 & 0 & 4 & 0 & 5 & 0 & 8 & 0 & 10 & 0 & 8 & 0 & 5 & 22 \\
16 & 0 & 15 & 0 & 15 & 0 & 16 & 0 & 19 & 0 & 21 & 0 & 19 & 0 & 0 \\
0 & 5 & 0 & 4 & 0 & 4 & 0 & 5 & 0 & 8 & 0 & 10 & 0 & 8 & 22 \\
19 & 0 & 16 & 0 & 15 & 0 & 15 & 0 & 16 & 0 & 19 & 0 & 21 & 0 & 0 \\
0 & 8 & 0 & 5 & 0 & 4 & 0 & 4 & 0 & 5 & 0 & 8 & 0 & 10 & 22 \\
0 & 22 & 0 & 22 & 0 & 22 & 0 & 22 & 0 & 22 & 0 & 22 & 0 & 22 & 77 \\
\end{array}
\right)
\end{array}$$
Now we give the sum of all these upper-triangular entries. There are four diagonals that appear once in the matrix. The entries of the first such diagonal are n + 12 and 8 and each of these appear n–1 times, and so there sum is (n–1)(n + 12) + 8(n–1). The entries of the second such diagonal are n + 9 and 5 and each of these appear n–2 times, and so there sum is (n–2)(n + 9) + 5(n–2). The entries of the third such diagonal are n + 9 and 5 and each of these appear 2 times, and so there sum is 2n + 28. The entries of the fourth such diagonal are n + 12 and 8 and each of these appears 1 time, and so there sum is n + 20.
Now we find the sum of those n–5 diagonals whose entries are same but appear with different number of times. Each such diagonal has two types of entries, n + 8 and 4. The largest of these diagonals contains n–3 entries of value n + 8, the next contains n–4 entries of value n + 8, and so on the last such diagonal contains 3 entries. Thus the sum of all these entries is
$$\begin{array}{}
\displaystyle
Sum_{1} \!\!\!\!\!&= (n-3)(n+8)+ (n-4)(n+8)+\cdots + (3)(n+8)\\
\displaystyle
&= (n+8)[(n-3)+(n-4)+\cdots + 3]\\
\displaystyle
&= \frac{n}{2}(n+8)(n-5).
\end{array}$$
Similarly, since 4 appears the same number of times the n + 8 appears, their sum is Sum2 = 2n(n–5).
Since the entries 2n + 8 in the last column appear n times, their sum is n(2n + 8).
Finally, the sum of all upper-triangular entries of A4 is
$$\begin{array}{}
w_{4} \!\!\!\!\!&=\displaystyle \big[(n-1)(n+12)+8(n-1)\big]+\big[(n-2)(n+9)+5(n-2)\big]\\
&\displaystyle\quad+\big[2n+28\big]+\big[n+20\big]+\frac{n}{2}(n+8)(n-5)+2n(n-5)+n(2n+8)\\
&\displaystyle= \frac{1}{2}[n^{3}+15n^{2}+24n].
\end{array}$$