How to calculate square matrix to power n? I have a matrix of non-negative numbers, say $A$.
(1) How do we calculate $A^n$?
(2) How can we calculate $A^n$ using usual matrix exponential trick to do it fast ?
Edit 1
Also theres another property of matrix A that its diagonals consists always of 0 & other elements either 0 or 1. 
Can we do this just by involving matrix multiplication ?
 A: Another approach is called exponentiation by squaring. It still requires you to multiply out matrices like normal, but you only need $O(\log n)$ such multiplications.
This approach is most useful if you want a few values for $A^k$ with $k$ large. But if you want the values of $A^k$ for a sequence of values $k=0,1,\dots$ it is isn't much help.
A: Using eigenvalues $\lambda_\pm$ of an $2 \times 2$ matrix $\textbf{A}$, you can find the expression
$$\textbf{A}^\zeta = \frac{\lambda_+^\zeta - \lambda_-^\zeta}{\lambda_+ - \lambda_-} \textbf{A} - \lambda_+ \lambda_- \frac{\lambda_+^{\zeta-1} - \lambda_-^{\zeta-1}}{\lambda_+ - \lambda_-} \textbf{I}$$
http://xphysics.wordpress.com/2011/12/03/raising-the-power-of-a-2%c3%972-matrix/
A: You may use Cayley-Hamilton Theorem which states every matrix satisfies its characteristic polynomial. 
Suppose you have a $k\times k$ matrix $A$.
In order to find $A^n$  for a large n, you divide $x^n$ by $P(x)$, the characteristic polynomial to get a remainder $R(x)$ which has degree less than $k$. 
Note that $ A^n = P(A)Q(A)+R(A) = R(A)$  where R(A) is easy to find. 
For example if $n=100$ and $k=3$ then $R(x)$ is a polynomial of second degree.    
A: One method is induction. Another way to calculate $A^{n}$ for a $2 \times2$ matrix generally is the Hamilton-Cayley Theorem: $A^{2}-Tr(A)\cdot A +\det{A} \cdot I_{2}=0$. This is a very useful theorem which can be applied for any $n \times n$ matrix.
for example if you have a $2 \times 2$ matrix with $\det{A}=0$ and $Tr(A)=\alpha$, the Hamilton-Cayley theorem then becomes:
$$A^2=\alpha\cdot A.$$
$$A^3=\alpha\cdot A^{2}=\alpha^{2}\cdot A$$
$$\vdots$$
$$A^{n}=\alpha^{n-1}\cdot A$$
This is a particular answer, but I recommend the following book (Matrix analysis - Roger Horn). If you have any problem to view this book, tell me.
EDIT:
Another way to calculate the power of matrix is binomial theorem.
you will try to write your initial matrix $A$ like $A_{1}+I$ and then to observe a number $p$ for that $A_{1}^{p}=O. $
