Let $A$=[$a_{ij}$]$_{n x n}$ where $a_{ii}$=$1$, $i=\overline {1,n}$, $a_{ij}=a\not=1, i\not=j$. Find $A^n$, $n\in \mathbb N$

Problem: Let $A$=[$a_{ij}$]$_{n x n}$ where $a_{ii}$=$1$, $i=\overline {1,n}$, $a_{ij}=a\not=1, i\not=j$. Find $A^n$, $n\in \mathbb N$.

I need a little help solving this problem. Now, I know how to find $A^n$ if this was matrix 2 by 2, or 3 by 3. I know there is a way to find the eigenvalues and the eigenvectors and form the matrices $P$ (made of eigenvectors) and $D=diag(\lambda_1,...,\lambda_n)$ using $A^n$=$PD^n$$P^{-1} (correct me if I am wrong). However, I do not know how to find the eigenvalues and eigen vectors. So, I tried this: My matrix A would have this form:$$A= \begin{bmatrix} 1 & a & a & \cdots &a \\ a & 1 & a &\cdots &a \\ \vdots & \vdots &\vdots &\ddots&\vdots\\ a & a & a &\cdots &1 \\ \end{bmatrix} $$So, that is symmetric matrix. If I look at my rows, I see that sum of all elements in each row is (n-1)a+1. Could I then say that my eigenvalue is (n-1)a+1 ? I was thinking about using A^n\overrightarrow v=\lambda^n \overrightarrow v, where \overrightarrow v is my eigenvector, to get the result but I am really not sure how to go from here. Any help is greatly appreciated. • Yes you can indeed say that is an eigenvalue, using the fact that for v=\begin{bmatrix} 1\\1\\\vdots\\1\end{bmatrix}$$Av=((n-1)a+1)v$$. Think of other eigenvectors to find them all. But, in my opinion, the best way would be solving the equation$$\det(A-\lambda I)=0$$, as the roots \lambda would be the eigenvalues. In particular, this new matrix looks a lot like yours, only the diagonal entries are different. – Emre Jun 2, 2016 at 1:03 1 Answer Continuing from the comment I provided:$$A-\lambda I=\begin{pmatrix} 1-\lambda&a&\cdots&a\\ a&1-\lambda&\cdots&a\\ \vdots&\vdots&\ddots&\vdots\\ a&a&\cdots&1-\lambda \end{pmatrix} $$We want this matrix to be singular. We already know that making the diagonals -(n-1)a makes it singular. Trying out for n=2, one can immediately see that making all the diagonals equal to a also works. This second possibility corresponds to the eigenvalue 1-a. These are the only eigenvalues, as v_i=(1,0,\ldots,0,\overbrace{-1}^\text{i-th place},0,\ldots,0) are for i=2,\ldots, n are the eigenvectors for \lambda=1-a. So, we have$$P=\begin{pmatrix} 1&1&1&\ldots&1\\ 1&-1&0&\ldots&0\\ 1&0&-1&\ldots&0\\ \vdots&\vdots&\vdots&\ddots&\vdots\\ 1&0&0&\ldots&-1 \end{pmatrix}\qquad D=\begin{pmatrix} (n-1)a+1&0&0&\ldots&0\\ 0&1-a&0&\ldots&0\\ 0&0&1-a&\ldots&0\\ \vdots&\vdots&\vdots&\ddots&\vdots\\ 0&0&0&\ldots&1-a \end{pmatrix}$$After some calculation, one can see that$$P^{-1}=\frac1n\begin{pmatrix} 1&1&1&\ldots&1\\ 1&1-n&1&\ldots&1\\ 1&1&1-n&\ldots&1\\ \vdots&\vdots&\vdots&\ddots&\vdots\\ 1&1&1&\ldots&1-n \end{pmatrix}$$Let c=(1-a)^n and b=((n-1)a+1)^n. Then,$$A^n=PD^nP^{-1}=\frac1n\begin{pmatrix} b+(n-1)c&b-c&b-c&\ldots&b-c\\ b-c&b+(n-1)c&b-c&\ldots&b-c\\ b-c&b-c&b+(n-1)c&\ldots&b-c\\ \vdots&\vdots&\vdots&\ddots&\vdots\\ b-c&b-c&b-c&\ldots&b+(n-1)c \end{pmatrix}$$• Thank you very much! I have one more question. After I have$P$and$D$, do I continue to find$P^{-1}$, and then calculate$PD^nP^{-1}$or is there some better way to find$A^n$? Jun 2, 2016 at 17:45 • My first attempt would be to calculate$A^n$for$n=1,2,3,4$and to figure out the pattern. But, calculating$D^N$,$P^{-1}\$ and multiplying them is not that hard either.
– Emre
Jun 2, 2016 at 17:50
• I edited the solution, hope this helps.
– Emre
Jun 2, 2016 at 18:27