Please remember me a reference of following method in computation of minimal polynomial of matrix.

Already, I saw a method for computing minimal polynomial of matrix in some text. I want its reference?

The method is as follow: Let us consider matrix $A= ‎\begin{bmatrix} 1 & 2 \\‎ 3 & 4 \end{bmatrix}$. We form $A^0=I,A^1,A^2$, so we have:

$$A^0=I= ‎\begin{bmatrix} 1 & 0 \\‎ 0 & 1 \end{bmatrix},\ A^1= ‎\begin{bmatrix} 1 & 2 \\‎ 3 & 4 \end{bmatrix},\ A^2= ‎\begin{bmatrix} 5 & 10 \\‎ 15 & 22 \end{bmatrix}.$$

Then form a following matrix $B$ using $A^0,A^1,A^2$ s.t. i'th column of $B$ is arrays of $A^i$. So we have:

$$B= ‎\begin{bmatrix} 1 & 1 & 7\\‎ 0 & 2 & 10\\ 0 & 3 & 15\\ 1 & 4 & 22 \end{bmatrix}.$$

The Gaussian elimination matrix of $B$ is matrix $C$ as follow:

$$C= ‎\begin{bmatrix} 1 & 1 & 7\\‎ 0 & 2 & 10\\ 0 & 0 & 0\\ 0 & 0 & 0 \end{bmatrix}.$$

The minimal polynomial of $A$ is $f(x)=x^2+a_1x+a_0$ where $a_0,a_1$ are obtained from following system: $$a_0+a_1+7=0, ~0\cdot a_0+2a_1+10=0.$$ So we have $a_0=-2,a_1=-5$. Therefore $$f(x)=x^2-5x-2.$$ Could you please help me to remember some text that this method be presented in it?

Thank you so much.

• This method is not completely accurate, for you want to find the smallest $n$ such that $A^0, A, A^2, \dots, A^n$ are linearly dependent. Using your Gaussian elimination you will then end up getting $a_0, \dots, a_n$ such that $\sum_{i = 1}^n a_i A^i = 0$ and $a_n = 1$. So $f = \sum_{i = 1}^n a_i x^i$ will be a polynomial with $f(A) = 0$ and then because of the minimality of $n$ it is the minimal polynomial. Your example worked because $n = 2$ turned out to be the minimal $n$, but for $A$ the zero matrix you would already have to stop at $n = 1$. – Matthias Klupsch Dec 17 '15 at 8:34
• This method is completely accurate! I implemented this algorithm for n*n matrix and for the zero matrix it's minimal polynomial is $x$. I know it's correction and I want to know it's reference only. – mahdi dehghani Dec 17 '15 at 8:53
• I know that your question is about a reference (you might consider adding the tag (reference-request)). I just wanted to point out that the way you presented the algorithm in your question it would lead to incorrect results in the sense that if I follow your procedure word for word with another matrix $A$, then I would not always get the minimal polynomial (because in the end it says that the minimal polynomial is of the form $f(x) = x^2 + a_1 x + a_0$ which is not always the case). It is good if you know that, but others might be confused. – Matthias Klupsch Dec 17 '15 at 9:29
• Yes in this example $n=2$ which is the rank of Gaussian elimination matrix. In general, degree of $f$ is equal to the rank of Gaussian elimination matrix. Is this true? – mahdi dehghani Dec 17 '15 at 9:44
• Yes, this is true. In fact, if this matrix has rank $r$ then the first $r$ columns of it will be linear independent and the relation between the first $r +1$ derived by Gaussian elimination will give you the minimal polynomial. – Matthias Klupsch Dec 17 '15 at 12:34