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 ?

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.

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. $

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/

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.