A First Course in Linear Algebra: Late Determinants (Beta)

Base Case.

When \(A\) is a \(1\times 1\) matrix, the number zero is on the diagonal zero times or one time. In the first case, the matrix is nonsingular, so \(\nsp{A^1}\) is trivial and its dimension is zero. In the second case, the matrix is the zero matrix and \(\nsp{A^1}=\complex{1}\) with dimension one—equal to the number of zeros on the diagonal of \(A\text{.}\)

Induction Step.

The similarity of \(A\) and \(T\) implies there is a nonsingular matrix \(S\) such that \(AS=ST\text{.}\) Let \(\vectorlist{x}{n}\) be the columns of \(S\text{.}\) In order to apply the induction step, we adjust this matrix equality by removing the last column from the matrix on each side of the equality. Specifically, define \(\widehat{S}\) to be the \(n\times n-1\) matrix whose columns are \(\vectorlist{x}{n-1}\text{.}\) Define \(\widehat{T}\) to be the \(n-1\times n-1\) matrix obtained from \(T\) be removing the last column and the last row. \(T\) is upper triangular so all but the last entry of the last row is zero, so the \(n-1\) columns of \(\widehat{S}\widehat{T}\) equal the first \(n-1\) columns of \(ST\text{,}\) and we can write a key equation,

And a key consequence is,

Note that \(\widehat{T}\) is an \(n-1\times n-1\) upper triangular matrix which is similar to itself (Theorem SER). So applying the induction hypothesis, we see that the number of zeros on the diagonal of \(\widehat{T}\) is equal to the dimension of \(\nsp{\widehat{T}^{n-1}}\text{.}\) By Theorem NSPM, and since \(\widehat{T}\) has size \(n-1\) we also have \(\dimension{\nsp{\widehat{T}^{n-1}}} = \dimension{\nsp{\widehat{T}^{n}}}\text{.}\)

Let \(U=\spn{\vectorlist{x}{n-1}}\text{,}\) which is the column space of \(\widehat{S}\) (A-invariant noted?). We claim that

Let \(\set{\vectorlist{w}{k}}\) be a basis for the subspace \(U\cap\nsp{A^n}\) of \(\complex{n}\text{.}\) Because \(\vect{w}_i\in U\) there is a vector \(\vect{v}_i\in\complex{n-1}\) such that \(\vect{w}_i=\widehat{S}\vect{v}_i\text{.}\) It is an exercise to prove that \(\set{\vectorlist{v}{k}}\) is a linearly independent set. Now,

Because the columns of \(\widehat{S}\) are linearly inependent, we conclude that \(\widehat{T}^n\vect{v}_i = \zerovector\) and thus \(\vect{v}_i\in\nsp{\widehat{T}^n}\text{.}\) So we have found at least \(k\) linearly independent vectors in \(\nsp{\widehat{T}^n}\) and thus

For the opposite inequality, let \(\set{\vectorlist{y}{\ell}}\) be a basis for the subspace \(\nsp{\widehat{T}^{n}}\) of \(\complex{n-1}\text{.}\) By a very similar exercise to the previous one, \(\set{\widehat{S}\vect{y}_1,\,\widehat{S}\vect{y}_2,\,\widehat{S}\vect{y}_3,\dots,\widehat{S}\vect{y}_\ell}\) is a linearly independent set. Note that each vector is a linear combination of the columns of \(\widehat{S}\) and so an element of \(U\text{.}\) Also

So each vector is also in \(\nsp{A^n}\text{.}\) Therefore we have found \(\ell\) linearly independent vectors in the subspace \(U\cap\nsp{A^n}\text{,}\) so

Note that \(\widehat{T}\) is an \(n-1\times n-1\) upper triangular matrix which is similar to itself (Theorem SER). So applying the induction hypothesis, we see that the number of zeros on the diagonal of \(\widehat{T}\) is equal to the dimension of \(\nsp{\widehat{T}^{n-1}}\text{.}\) By Theorem NSPM, and since \(\widehat{T}\) has size \(n-1\) we also have \(\dimension{\nsp{\widehat{T}^{n-1}}} = \dimension{\nsp{\widehat{T}^{n}}}\text{.}\)

So we are close! Let's take stock of where we are. We know \(U\) has dimension \(n-1\text{.}\) We do not know much yet about the subspace \(U + \nsp{A^n}\)—however its dimension is limited to two possibilities: \(n-1\) or \(n\text{.}\) So \(\dimension{U + \nsp{A^n}} - \dimension{U}\) is \(0\) or \(1\text{.}\) We know \(\dimension{\nsp{\widehat{T}^{n}}}\) counts zeros on the diagonal of \(\widehat{T}\text{.}\) There is only the final diagonal entry of \(T\) to consider: the entry is nonzero and the count increases by \(0\text{,}\) or the entry is zero and the count increases by \(1\text{.}\) We finish the proof by showing that these two zero-one scenarios are the same.

First, suppose the final entry of the diagonal of \(T\) is nonzero and equal to \(a\text{.}\) We claim that \(\nsp{A^n}\subseteq U\text{.}\) The final diagonal entry of \(T^n\) is \(a^n\text{,}\) and since \(A^nS = ST^n\text{,}\) there is a \(\vect{u}\in U\) such that

Grab an arbitrary \(\vect{z}\in\nsp{A^n}\) and since the columns of \(S\) are a basis, we can write \(\vect{z}=\widehat{\vect{u}} + b\vect{x}_n\text{,}\) where \(\widehat{\vect{u}}\in U\text{.}\) Now

Because \(U\) is an \(A\)-invariant subspace, the first term is a vector in \(U\text{,}\) and so is the second. Additive closure for \(U\text{,}\) plus a rearrangement, makes it clear that \(ba^n\vect{x}_n\in U\text{.}\) This is only possible if this vector is the zero vector, and since we are assuming \(a\neq 0\text{,}\) we conclude that \(b=0\text{.}\) Thus \(\vect{z}=\widehat{\vect{u}}\in U\text{,}\) establishing our claim, and we see that \(U + \nsp{A^n} = U\text{.}\) So,

Second, suppose the final entry of the diagonal of \(T\) is zero. We claim that \(U + \nsp{A^n} = \complex{n}\text{,}\) which will be true if we can find a vector in \(\nsp{A^n}\) that lies outside of \(U\text{.}\) The last column of the equality \(AS = ST\text{,}\) together with the form of the last column of \(T\) in this case, implies that \(A\vect{x}_n\) is a linear combination of the first \(n-1\) columns of \(S\text{.}\) So there is a vector \(\vect{y}\in\complex{n-1}\) such that \(A\vect{x}_n = \widehat{S}\vect{y}\text{.}\) \(\nullity{\widehat{T}^{n-1}} = \nullity{\widehat{T}^n}\text{,}\) so \(\rank{\widehat{T}^{n-1}} = \rank{\widehat{T}^n}\) by Theorem RPNC. Null spaces of powers of a matrix increase in size, while column spaces of powers decrease in the same manner (see Exercise IS.T31), and since \(\widehat{T}\) is a matrix of size \(n-1\text{,}\) we have \(\csp{\widehat{T}^{n-1}}=\csp{\widehat{T}^n}\text{.}\) \(\widehat{T}^{n-1}\vect{y}\in\csp{\widehat{T}^{n-1}}=\csp{\widehat{T}^n}\text{.}\) So there is a vector \(\vect{w}\in\complex{n-1}\) such that \(\widehat{T}^{n-1}\vect{y} = \widehat{T}^n\vect{w}\text{.}\) The vector we are after is \(\vect{z}=\widehat{S}\vect{w} - \vect{x}_n\text{,}\) as we will now show. We see that \(\widehat{S}\vect{w}\) is in \(U\) and \(\vect{x}_n\) is not in \(U\text{,}\) so it would be a contradiction if \(\vect{z}\) were in \(U\text{,}\) so \(\vect{z}\not\in U\text{.}\) Consider

So there is an element of \(\nsp{A^n}\) outside of \(U\text{,}\) so the dimension of \(U + \nsp{A^n}\) must be strictly greater than the dimension of \(U\text{,}\) which only leaves \(\dimension{U + \nsp{A^n}} = n\) and so \(U + \nsp{A^n} = \complex{n}\text{.}\) We have,

So for the two possibilities for \(\dimension{U + \nsp{A^n}}\text{,}\) \(n-1\) and \(n\text{,}\) we have the same conclusion: the number of zeros on the diagonal of \(T\) is equal to the dimension of the null space of \(A^n\text{.}\)

We have been simply counting zeros on the diagonal, without considering whether or not they are even eigenvalues. It is a simple matter to get back to eigenvalues. For an eigenvalue \(\lambda\) of \(A\text{,}\) the upper triangular matrix \(T - \lambda I_n\) is similar to \(A-\lambda I_n\) by Theorem PSMS with the polynomial \(p(x)=x-\lambda\text{.}\) So we can apply the above results to \(A-\lambda I_n\) and \(T-\lambda I_n\text{.}\) The number of times an eigenvalue of \(A\) appears on the diagonal of \(T\) is the number of times zero appears on the diagonal of \(T - \lambda I_n\text{,}\) which is the dimension of the null space of \(\left(A - \lambda I_n\right)^n\text{,}\) the algebraic multiplicity of \(\lambda\) for \(A\text{.}\)

Generalized eigenspaces are disjoint.

Informally, we claim a generalized eigenvector cannot serve two eigenvalues. More precisely, suppose \(\lambda\) and \(\rho\) are two different eigenvalues of \(A\text{.}\) Then \(\geneigenspace{A}{\lambda}\cap\geneigenspace{A}{\rho} = \set{\zerovector}\text{.}\) The more specific result for traditional eigenvectors is Exercise PEE.T20.

For a proof by contradiction (Proof Technique CD), suppose that

Then there is a minimal \(k\) such that \(\left(A - \lambda I_n\right)^k\vect{v} = \zerovector\text{.}\) Since \(\vect{v}\neq\zerovector\text{,}\) \(k\geq 1\text{.}\) Define

The minimality of \(k\) implies that \(\vect{w}\neq\zerovector\text{.}\)

Now, since

we see that \(\vect{w}\) is a traditional eigenvector of \(A\) for \(\lambda\text{.}\)

We claim \(\vect{w}\) is a generalized eigenvector of \(A\) for \(\rho\text{.}\) We establish by induction a more general claim:

For the base case, when \(i=0\text{,}\) \(\vect{v}\in\geneigenspace{A}{\rho}\) follows from our choice of \(\vect{v}\text{.}\) More generally,

By induction, \(\vect{w}_{i-1}\in\geneigenspace{A}{\rho}\text{,}\) which is an \(A\)-invariant subspace (Theorem GEIS), and so \(A\vect{w}_{i-1}\in\geneigenspace{A}{\rho}\text{.}\) By scalar closure, \(\lambda\vect{w}_{i-1}\in\geneigenspace{A}{\rho}\text{.}\) So additive closure then shows that \(\vect{w}_i\in\geneigenspace{A}{\rho}\text{,}\) as desired.

Since \(\vect{w}\) is a generalized eigenvector of \(A\) for \(\rho\text{,}\)

Since \(\lambda\) and \(\rho\) are by hypothesis different, \(\left(\lambda - \rho\right)^n\neq 0\text{,}\) and we argued above that \(\vect{w}\neq\zerovector\text{.}\) So the previous equation and Theorem SMEZV gives the desired contradiction.

Generalized eigenvectors for distinct eigenvalues are linearly independent.

This is a generalization of Theorem EDELI. Suppose that \(S=\set{\vectorlist{x}{p}}\) is a set of generalized eigenvectors of \(A\) with eigenvalues \(\scalarlist{\lambda}{p}\) such that \(\lambda_i\neq\lambda_j\) whenever \(i\neq j\text{.}\) Then we claim that \(S\) is a linearly independent set.

We argue by induction on \(k\) (Proof Technique I) with the induction hypothesis that any set of \(k\) generalized eigenvectors of \(A\text{,}\) \(\set{\vectorlist{x}{k}}\text{,}\) for different eigenvalues \(\scalarlist{\lambda}{k}\text{,}\) is linearly independent.

When \(k=1\text{,}\) the set \(\set{\vect{x}_1}\) is linearly independent since eigenvectors are nonzero (Definition EEM).

For the induction step begin with a relation of linear dependence

and then

Since \(\vect{x}_i\text{,}\) \(1\leq i\leq k-1\text{,}\) is not a generalized eigenvector for \(\lambda_k\text{,}\) we have \(\left(A - \lambda_k I_n\right)^n \vect{x}_i\neq\zerovector\text{.}\) Furthermore, we claim each of these nonzero vectors is a generalized eigenvector for \(\lambda_i\text{.}\) To wit,

and so \(\left(A - \lambda_k I_n\right)^n \vect{x}_i\in\geneigenspace{A}{\lambda_i}\text{.}\) So above we have a relation of linear dependence on the set \(\set{\left(A - \lambda_k I_n\right)^n \vect{x}_1, \ldots, \left(A - \lambda_k I_n\right)^n \vect{x}_{k-1}}\text{,}\) which is a set of \(k-1\) generalized eigenvectors for distinct eigenvalues, and hence by the induction hypothesis is linearly independent. By Definition LI, \(a_1=a_2=\cdots=a_{k-1}=0\text{.}\) The original relation of linear dependence then simplifies to \(a_k\vect{x}_k = \zerovector\text{.}\) Because \(\vect{x}_k\neq\zerovector\text{,}\) Theorem SMEZV implies \(a_k=0\text{.}\) So the only relation of linear dependence on the set of \(k\) generalized eigenvectors is trivial, so by Definition LI, the set is linearly independent.

A basis of generalized eigenvectors.

Let \(\scalarlist{\lambda}{k}\) be a complete list of the distinct eigenvalues of \(A\text{.}\) For each generalized eigenvalue, and for convenience, let \(m_i = \algmult{A}{\lambda_i}\text{.}\) For each generalized eigenspace choose a basis

and define our putative basis of \(\complex{n}\) as

Because a vector cannot simultaneously be a generalized eigenvector for two different eigenvalues, and employing Theorem NEM, the number of vectors in \(B\) is given by

So we have a set of \(n\) vectors from \(\complex{n}\) and Theorem G tells us \(B\) will be a basis of \(\complex{n}\) if we can show that \(B\) is linearly independent.

So we form a relation of linear dependence on \(B\text{,}\) using doubly-subscripted scalars and generalized eigenvectors,

Define the vectors \(\vect{y}_i\text{,}\) \(1\leq i\leq k\) by

Then the relation of linear dependence becomes

Since the generalized eigenspace \(\geneigenspace{A}{\lambda_i}\) is closed under vector addition and scalar multiplication, \(\vect{y}_i\in\geneigenspace{A}{\lambda_i}\text{,}\) \(1\leq i\leq k\text{.}\) Thus, for each \(i\text{,}\) the vector \(\vect{y}_i\) is a generalized eigenvector of \(A\) for \(\lambda_i\text{,}\) or is the zero vector. We proved above that sets of generalized eigenvectors whose eigenvalues are distinct form a linearly independent set. Should any (or some) \(\vect{y}_i\) be nonzero, the previous equation would provide a nontrivial relation of linear dependence on a set of generalized eigenvectors with distinct eigenvalues, contradicting the result in our second step. Thus \(\vect{y}_i=\zerovector\text{,}\) \(1\leq i\leq k\text{.}\)

Each of the \(k\) equations, \(\vect{y}_i=\zerovector\text{,}\) is a relation of linear dependence on the corresponding set \(B_i\text{,}\) a set of basis vectors for the generalized eigenspace \(\eigenspace{A}{\lambda_i}\text{,}\) which is therefore linearly independent. From these relations of linear dependence on linearly independent sets we conclude that the scalars are all zero, more precisely, \(a_{ij}=0\text{,}\) \(1\leq j\leq m_i\text{,}\) \(1\leq i\leq k\text{.}\) This establishes that our original relation of linear dependence on \(B\) has only the trivial relation of linear dependence, and hence \(B\) is a linearly independent set, and a basis of \(\complex{n}\text{.}\)

(⇒) 

If \(A\) is diagonalizable then by Theorem DC there is a set of \(n\) linearly independent eigenvectors of \(A\text{.}\) Let \(n_i\) be the number of eigenvectors from this set that are associated to eigenvalue \(\lambda_i\text{.}\) Each individual group of eigenvectors will be linearly independent, so by Theorem G its size cannot exceed the dimension of the eigenspace they belong to. So \(n_i\leq\geomult{A}{\lambda_i}\text{.}\)

Then, application of Theorem ME and Theorem NEM gives

With \(n\) at each end of this string of inequalities, each expression must be equal to the others. In particular, the application of Theorem ME implies that \(\geomult{A}{\lambda_i}=\algmult{A}{\lambda_i}\) for \(1\leq i\leq t\text{.}\)

(⇐) 

If \(\geomult{A}{\lambda_i}=\algmult{A}{\lambda_i}\text{,}\) then by Theorem EDYES \(\eigenspace{A}{\lambda_i}=\geneigenspace{A}{\lambda_i}\text{,}\) so every generalized eigenvector is a traditional eigenvector. Theorem GEB guarantees a basis of \(\complex{n}\) composed of generalized eigenvectors of \(A\text{.}\) This is a set of \(n\) linearly independent eigenvectors for \(A\text{,}\) so by Theorem DC, \(A\) is diagonalizable.

Base Case.

When \(k=1\text{,}\) we need only show consider \((T-\lambda_1 I_n)\vect{e}_1\text{.}\) Owing to the upper triangular nature of \(T\text{,}\) the first column of \(T-\lambda_1 I_n\) is the zero vector and the matrix-vector product with \(\vect{e}_1\) is just this column.

Induction Step.

For \(1\leq i\leq k-1\text{,}\)

For \(i=k\text{,}\) notice that the upper triangular nature of \(T\) implies that column \(k\) of \(T-\lambda_k I_n\) begins with \(k-1\) entries of any variety, followed by \(n-k+1\) entries that are zero. So there are scalars \(\scalarlist{b}{k-1}\) such that

Then

So we have established the claim for all \(1\leq i\leq k\text{.}\)