Powers of a matrix, largest required collection for linear dependence to occur, reduction to vectors Consider the dependence equation
$$
A^m + c_1A^{m-1}+...+c_{m-1}A + c_mI = 0
$$
where $A \in \Bbb{R}^{n \times n}$ and $I$ is the identity matrix. Asked to show that there exists an $m> 0$ such that some choice of $c_i$ yields a solution we note that the dimension of the vector  space of square matrices is $n^2$ and that therefore, at the latest, $m>n^2-1$ yields a solution.
My question relates to this: If we chose to multiply on the right by some general $x \in \Bbb{R}^n$ such that
$$
A^mx + c_1A^{m-1}x+...+c_{m-1}Ax + c_mIx = 0
$$
we have $m+1$ vectors and seek a linear dependence relation among them. Then we would say that dependence is achieved at the latest when $m>n-1$. Square matrices say something about transformations of a vector space as I understand it. Yet I can not quite grasp where the loss of information comes from. What goes wrong when we right multiply by $x$, reducing it to a question about vectors instead of matrices? Does it have something to do with only considering one x instead of a set of vectors spanning the underlying space? Thanks in advance.
 A: As remarked in another answer, the Cayley-Hamilton theorem provides an explicit set of coefficients (in terms of $A$) for which such a relation holds, with $m=n$. But you can deduce the existence of such a relation, with $m\leq n$, from the relation deduced for arbitrary $x\in\Bbb{R}^n$ in the second part of your argument; this does not involve determinants and such.
A first thing to do is reformulate the dependency relations in terms of polynomials: with the degree$~m$ unitary polynomial $P=X^m+c_1X^{m-1}+\cdots+c_{m-1}X+c_m$, the relations are $P[A]=0$ (the zero matrix) respectively $P[A]x=0$ (the zero vector). An advantage of this formulation is that one easily shows that such a relation implies any similar relation obtained by replacing $P$ by a polynomial multiple $PQ$.
A relation $P[A]x=0$ for a particular $x\in\Bbb R^n$ is weaker than $P[A]=0$, so it is not surprising that the argument proving existence of unitary $P$ of degree at most$~n$ satisfying the former relation does not work for proving the same for the latter relation. The former relation can also be written $x\in\ker(P[A])$, and if one would simply apply it for $x$ traversing a basis of$~\Bbb R^n$, one would get $n$ different corresponding polynomials$~P$, each of degree at most$~n$, and taking their least common polynomial multiple $M$ this gives $\ker(M[A])=\Bbb R^n$, so $M[A]=0$. But then one could only say that $\deg(M)\leq n^2$ (since the least common multiple could be the product), so it would be no better than what is obtained by the direct argument given in the question.
But one can do better, since having $P[A]x=0$ with $P$ unitary of minimal degree gives more than one nonzero vector in $\ker(P[A])$; indeed it gives $\dim\ker(P[A])\geq\deg(P)$. Once this is established, one can argue the existence of unitary $Q$ with $Q[A]=0$ and $\deg(Q)\leq n$ as follows by induction on the dimension. If $\deg(P)=n$ (which is quite often the case), one can simply take $Q=P$. Otherwise the image $W$ of $P[A]$ is a subspace of dimension (by rank nullity) $d=n-\dim\ker(P[A])\leq n-\deg(P)$, and closed under multiplication by$~A$. The induction hypothesis, applied to the subspace$~W$ and a matrix that expresses multiplication by $A$ on a basis of$~W$, then gives a unitary polynomial $P'$ with $\deg(P')\leq d$ such that $W\subseteq\ker(P'[A])$. Setting $Q=P'P$ one has $Q[A]=P'[A]\cdot P[A]=0$ while $\deg(Q)\leq d+\deg(P)\leq n$, so $Q$ satisfies the requirement.
Finally, the inequality $\dim\ker(P[A])\geq\deg(P)$ used above is based on the fact that with $P[A]x=0$ one also has, for every $k\in\Bbb N$, that $P[A](A^kx)=(PX^k)[A]x=0$ (since $PX^k$ is a multiple of $P$). Of these vectors $A^kx$ that lie in $\ker(P[A])$, the first $\deg(P)$ (namely $x$, $Ax$, $A^2x$, ... $A^{\deg(P)-1}x$) are linearly independent by the minimality of $\deg(P)$ (a linear dependence would provide a lower degree polynomial). This establishes the inequality.
A: Actually, Cayley-Hamilon implies the characteristic polynomial $\chi_A$ of $A$ annihilates $A$. Since $\deg \chi_A = n$, we conclude that the set $\{I,A,A^2, \ldots, A^n\}$ is linearly dependent so at the latest $m > n-1$ yields a solution, same as your vectors.
