Raising the bar

Conditional expectation as a projector

This topic was discussed here and here. Looks like my explanations were not sufficient for some students, so here I give it a second try.

Examples of projectors

The name "projector" is almost self-explanatory. Imagine a point and a plane in the three-dimensional space (see the Wolfram embedded notebook below). Draw a perpendicular from the point to the plane. The intersection of the perpendicular with the plane is the point's projection onto that plane. Note that if the point already belongs to the plane, its projection equals the point itself. Besides, instead of projecting onto a plane we can project onto a straight line.

The above description translates into the following equations. For any point $latex (x,y,z)\in R^{3}$ define

(1) $latex P_{1}(x,y,z)=(x,0,0)$ and $latex P_{2}(x,y,z)=(x,y,0).$

In words: $latex P_{1}$ leaves the first two coordinates of the point unchanged and sets the third one to zero. (Describe yourself what $latex P_{2}$ does.)

$latex P_{2}$ projects $latex R^{3}$ onto the plane $latex L_{2}=\{(x,y,0):x,y\in R\}$ (which is two-dimensional) and $latex P_{1}$ projects $latex R^{3}$ onto the straight line $latex L_{1}=\{(x,0,0):x\in R\}$ (which is one-dimensional).

Property 1. Double application of a projector amounts to single application.

Proof. Using (1) three times we get

(1) $latex P_{2}[P_{2}(x,y,z)]=P_{2}(x,y,0)=(x,y,0)=P_{2}(x,y,z).$

Similarly, $latex P_{1}[P_{1}(x,y,z)]=P_{1}(x,y,z).$

Property 2. A successive application of two different projectors yields the projection onto a subspace of a smaller dimension.

Proof. If we apply first $latex P_{2}$ and then $latex P_{1}$, the result is

(2) $latex P_{1}[P_{2}(x,y,z)]=P_{1}(x,y,0)=(x,0,0)=P_{1}(x,y,z).$

If we change the order of projectors, we have

(3) $latex P_{2}[P_{1}(x,y,z)]=P_{2}(x,0,0)=(x,0,0)=P_{1}(x,y,z).$

Informational interpretation

If we know $latex P_{2}(x,y,z)$ then we know more about the original point $latex (x,y,z)$ than if we know $latex P_{1}(x,y,z).$ Thus, $latex P_{1}$ projects onto a smaller information set than $latex P_{2}.$ Equations (2) and (3) can be summarized as follows: the smaller info set wins.

Exercise 1. Show that both projectors are linear.

Exercise 2. Like any other linear operator in a Euclidean space, these projectors are given by some matrices. What are they?

The simple truth about conditional expectation

In the time series setup, we have a sequence of information sets

$latex ... \subset I{t}\subset I_{t+1}\subset ...$

where $latex t$ are points in time (naturally, with time the amount of available information increases). Denote

$latex E_tX=E(X|I_t)$

the expectation of $latex X$ conditional on $latex I_{t}$.

Statement. For each $latex t$, $latex E_{t}$ is a projector onto the space of random functions that depend only on the information set $latex I_{t}$.

The proof is too complex to discuss here but the implications are immediate.

Property 3. Applying Property 1, we see that double application of conditional expectation gives the same result as single application:

(4) $latex E_t(E_tX)=E_tX$

($latex E_{t}X$ is already a function of $latex I_{t}$, so conditioning it on $latex I_{t}$ doesn't change it).

Property 4. A successive conditioning on two different information sets is the same as conditioning on the smaller one:

(5) $latex E_tE_{t+1}X=E_tX,$

(6) $latex E_{t+1}E_{t}X=E_{t}X.$

(5) and (6) apply also in the case $latex E_t=E$ because for the unconditional expectation the information set is empty.

These lead to more general equations. Suppose, $latex s\leq t-1<t.$ Then using (5) many times, we get

$latex E_{s}E_{t}X=E_{s}E_{s+1}E_{t}X=...=E_{s}E_{s+1}...E_{t-1}E_{t}X=E_{s}E_{s+1}...E_{t-1}X=...=E_{s}X.$

Property 5. Conditional expectation is a linear operator: for any random variables $latex X,Y$ and random variables $latex a,b$ that depend only on $latex I_t$ we have

$latex E_t(aX+bY)=aE_tX+bE_tY.$

I prefer to use different names for (4)-(6). I call (4) a projector property. (5) is known as the Law of Iterated Expectations, see my post on the informational aspect for more intuition. (6) holds simply because at time $latex t+1$ the expectation $latex E_{t}X$ is known and behaves like a constant.

Summary. (4)-(6) can be combined into one property. The smaller information set wins: for any points in time $latex s,t$ we have $latex E_{s}E_{t}X=E_{\min \{s,t\}}X.$

In the next Wolfram embedded notebook you can manipulate both graphs to get a better angle of view.

Distribution of the estimator of the error variance

If you are reading the book by Dougherty: this post is about the distribution of the estimator  $latex s^2$ defined in Chapter 3.

Consider regression

(1) $latex y=X\beta +e$

where the deterministic matrix $latex X$ is of size $latex n\times k,$ satisfies $latex \det
\left( X^{T}X\right) \neq 0$ (regressors are not collinear) and the error $latex e$ satisfies

(2) $latex Ee=0,Var(e)=\sigma ^{2}I$

$latex \beta $ is estimated by $latex \hat{\beta}=(X^{T}X)^{-1}X^{T}y.$ Denote $latex P=X(X^{T}X)^{-1}X^{T},$ $latex Q=I-P.$ Using (1) we see that $latex \hat{\beta}=\beta +(X^{T}X)^{-1}X^{T}e$ and the residual $latex r\equiv y-X\hat{\beta}=Qe.$ $latex \sigma^{2}$ is estimated by

(3) $latex s^{2}=\left\Vert r\right\Vert ^{2}/\left( n-k\right) =\left\Vert
Qe\right\Vert ^{2}/\left( n-k\right) .$

$latex Q$ is a projector and has properties which are derived from those of $latex P$

(4) $latex Q^{T}=Q,$ $latex Q^{2}=Q.$

If $latex \lambda $ is an eigenvalue of $latex Q,$ then multiplying $latex Qx=\lambda x$ by $latex Q$ and using the fact that $latex x\neq 0$ we get $latex \lambda ^{2}=\lambda .$ Hence eigenvalues of $latex Q$ can be only $latex 0$ or $latex 1.$ The equation $latex tr\left( Q\right) =n-k$
tells us that the number of eigenvalues equal to 1 is $latex n-k$ and the remaining $latex k$ are zeros. Let $latex Q=U\Lambda U^{T}$ be the diagonal representation of $latex Q.$ Here $latex U$ is an orthogonal matrix,

(5) $latex U^{T}U=I,$

and $latex \Lambda $ is a diagonal matrix with eigenvalues of $latex Q$ on the main diagonal. We can assume that the first $latex n-k$ numbers on the diagonal of $latex Q$ are ones and the others are zeros.

Theorem. Let $latex e$ be normal. 1) $latex s^{2}\left( n-k\right) /\sigma ^{2}$ is distributed as $latex \chi _{n-k}^{2}.$ 2) The estimators $latex \hat{\beta}$ and $latex s^{2}$ are independent.

Proof. 1) We have by (4)

(6) $latex \left\Vert Qe\right\Vert ^{2}=\left( Qe\right) ^{T}Qe=\left(
Q^{T}Qe\right) ^{T}e=\left( Qe\right) ^{T}e=\left( U\Lambda U^{T}e\right)
^{T}e=\left( \Lambda U^{T}e\right) ^{T}U^{T}e.$

Denote $latex S=U^{T}e.$ From (2) and (5)

$latex ES=0,$ $latex Var\left( S\right) =EU^{T}ee^{T}U=\sigma ^{2}U^{T}U=\sigma ^{2}I$

and $latex S$ is normal as a linear transformation of a normal vector. It follows that $latex S=\sigma z$ where $latex z$ is a standard normal vector with independent standard normal coordinates $latex z_{1},...,z_{n}.$ Hence, (6) implies

(7) $latex \left\Vert Qe\right\Vert ^{2}=\sigma ^{2}\left( \Lambda z\right)
^{T}z=\sigma ^{2}\left( z_{1}^{2}+...+z_{n-k}^{2}\right) =\sigma ^{2}\chi
_{n-k}^{2}.$

(3) and (7) prove the first statement.

2) First we note that the vectors $latex Pe,Qe$ are independent. Since they are normal, their independence follows from

$latex cov(Pe,Qe)=EPee^{T}Q^{T}=\sigma ^{2}PQ=0.$

It's easy to see that $latex X^{T}P=X^{T}.$ This allows us to show that $latex \hat{\beta}$ is a function of $latex Pe$:

$latex \hat{\beta}=\beta +(X^{T}X)^{-1}X^{T}e=\beta +(X^{T}X)^{-1}X^{T}Pe.$

Independence of $latex Pe,Qe$ leads to independence of their functions $latex \hat{\beta}$ and $latex s^{2}.$

Sylvester's criterion

Exercise 1. Suppose $latex A=CBC^{T},$ where $latex B=diag[d_{1},...,d_{n}]$ and $latex \det C\neq 0$. Then $latex A$ is positive if and only if all $latex d_{i}$ are positive.

Proof. For any $latex x\neq 0$ we have $latex x^{T}Ax=x^{T}CBC^{T}x=(C^{T}x)^{T}B(C^{T}x).$ Let $latex y=C^{T}x\neq 0.$ Then $latex x^{T}Ax=y^{T}By=\sum_{j}d_{j}y_{j}^{2}.$ This is positive for all $latex y\neq 0$ if and only if $latex \min_{j}d_{j}>0.$

Exercise 2 (modified Gaussian elimination). Suppose that $latex A$ is a real symmetric matrix with nonzero leading principal minors $latex d_{1},...,d_{n}$. Then $latex B=CAC^{T},$ where $latex B=diag[d_{1},d_{2}/d_{1},...,d_{n}/d_{n-1}]$ and $latex \det C=1$.

Proof. Review the transformation applied in Exercise 1 to obtain a triangular form. In that exercise, we eliminated element $latex a_{21}$ below $latex a_{11}$ by premultiplying $latex A$ by the matrix $latex C=I-\frac{a_{21}}{a_{11}} e_{2}^{T}e_{1}.$ Now after this we can post-multiply $latex A$ by the matrix $latex C^{T}=I-\frac{a_{21}}{a_{11}}e_{1}^{T}e_{2}.$ Because of the assumed symmetry of $latex A,$ we have $latex C^{T}=I-\frac{a_{12}}{a_{11}}e_{1}^{T}e_{2},$ so this will eliminate element $latex a_{12}$ to the right of $latex a_{11}$, see Exercise 2. Since in the first column $latex a_{21}$ is already $latex 0$, the diagonal element $latex a_{22}$ will not change.

We can modify Exercise 1 by eliminating $latex a_{1j}$ immediately after eliminating $latex a_{j1}.$ The right sequencing of transformations is necessary to be able to apply Exercise 1: the matrix used for post-multiplication should be the transpose of the matrix used for premultiplication. If $latex C=C_{m}...C_{1},$ then $latex C^{T}=C_{1}^{T}...C_{m}^{T},$ which means that premultiplication by $latex C_{i}$ should be followed by post-multiplication by $latex C_{i}^{T}.$ In this way we can make zero all off-diagonal elements. The resulting matrix $latex B=diag[d_{1},d_{2}/d_{1},$ $latex ...,d_{n}/d_{n-1}]$ is related to $latex A$ through $latex B=CAC^{T}.$

Theorem (Sylvester) Suppose that $latex A$ is a real symmetric matrix. Then $latex A$ is positive if and only if all its leading principal minors are positive.

Proof. Let's assume that all leading principal minors are positive. By Exercise 2, we have $latex A=C^{-1}B(C^{-1})^{T}$ where $latex \det C=1.$ It remains to apply Exercise 1 above to see that $latex A$ is positive.

Now suppose that $latex A$ is positive, that is $latex x^{T}Ax=\sum_{i,j=1}^{n}a_{ij}x_{i}x_{j}>0$ for any $latex x\neq 0.$ Consider cut-off matrices $latex A_{k}=\left( a_{ij}\right) _{i,j=1}^{k}.$ The corresponding cut-off quadratic forms $latex x^{T}A_{k}x=\sum_{i,j=1}^{k}a_{ij}x_{i}x_{j},$ $latex k=1,...,n,$ are positive for nonzero $latex x\in R^{k}.$ It follows that $latex A_{k}$ are non-singular because if $latex x\in N(A_{k}),$ then $latex x^{T}A_{k}x=0.$ Hence their determinants $latex d_{k}=\det A_{k},$ $latex k=1,...,n,$ are nonzero . This allows us to apply the modified Gaussian elimination (Exercise 2) and then Exercise 1 with $latex B=diag[d_{1},...,d_{n}/d_{n-1}].$ By Exercise 1 consecutively $latex d_{1}>0,$ $latex d_{2}>0,...,$ $latex d_{n}>0.$

Exercise 3. $latex A$ is negative if and only if the leading principal minors change signs, starting with minus: $latex d_{1}<0,$ $latex d_{2}>0,$ $latex d_{3}<0,...$

Proof. By definition, $latex A$ is negative if $latex -A$ is positive. Because of homogeneity of determinants, when we pass from $latex A$ to $latex -A,$ the minor of order $latex k$ gets multiplied by $latex (-1)^{k}.$ Thus, by Sylvester's criterion $latex A$ is negative if and only if $latex (-1)^{k}d_{k}>0,$ as required.

Gaussian elimination method

Consider the system

$latex a_{11}x+a_{12}y+a_{13}z=a_1,$

$latex a_{21}x+a_{22}y+a_{23}z=a_2,$

$latex a_{31}x+a_{32}y+a_{33}z=a_3.$

If the first equation is nontrivial, then one of the coefficients is different from zero. Suppose it is $latex a_{11}.$ Adding the first equation multiplied by $latex -a_{21}/a_{11}$ to the second one we eliminate $latex x$ from it. Similarly, adding the first equation multiplied by $latex -a_{31}/a_{11}$ to the third one we eliminate $latex x$ from it. The system becomes

$latex a_{11}x+a_{12}y+a_{13}z=a_1,$

$latex b_{22}y+b_{23}z=b_{2},$

$latex b_{32}y+b_{33}z=b_{3},$

where $latex b$ with indexes stands for new numbers.

If $latex b_{22}\neq 0,$ we can use the second equation to eliminate $latex y$ from the third equation and the result will be

$latex a_{11}x+a_{12}y+a_{13}z=a_{1},$

$latex b_{22}y+b_{23}z=b_{2},$

$latex c_{33}z=c_{3}$

with some new $latex c$'s. If $latex c_{33}\neq 0,$ we can solve the system backwards, finding first $latex z$ from the third equation, then $latex y$ from the second and, finally $latex x$ from the first.

Notice that for the method to work it does not matter what happens with the vector at the right of the system. It only matters what happens to $latex A.$ That's why we focus on transformations of $latex A.$

Theoretical treatment

Exercise 1. Denote

$latex d_{1}=a_{11},\ d_{2}=\det \left(\begin{array}{cc}
a_{11} & a_{12} \\a_{21} & a_{22}\end{array}\right) ,..., \ d_{n}=\det A$

the leading principal minors of $latex A.$ If all of them are different from zero, then the Gaussian method reduces $latex A$ (by way of premultiplication of $latex A$ by elementary matrices) to the triangular matrix

$latex B=\left(\begin{array}{cccc}b_{11} & b_{12} & ... & b_{1n} \\
0 & b_{22} & ... & b_{2n} \\... & ... & ... & ... \\0 & 0 & ... & b_{nn}\end{array}\right) $

where $latex b_{11}=d_{1},\ b_{22}=d_{2}/d_{1},...,\ b_{nn}=d_{n}/d_{n-1}.$

Proof by induction. Let $latex n=2.$ Premultiplying $latex A=\left(\begin{array}{cc}
a_{11} & a_{12} \\a_{21} & a_{22}\end{array}\right) $ by $latex I-\frac{a_{21}}{a_{11}}e_{2}^{T}e_{1}$ we get the desired result:

$latex B=\left(\begin{array}{cc}a_{11} & a_{12} \\0 & a_{22}-\frac{a_{21}a_{12}}{a_{11}}
\end{array}\right) =\left(\begin{array}{cc}d_{1} & a_{12} \\0 & \frac{d_{2}}{d_{1}}
\end{array}\right) .$

Now let the statement hold for $latex n-1.$ By the induction assumption we can start with the matrix of form

$latex A=\left(\begin{array}{ccccc}d_{1} & b_{12} & ... & b_{1n} & b_{1n} \\
0 & d_{2}/d_{1} & ... & b_{2n} & b_{2n} \\... & ... & ... & ... & ... \\0 & 0 & ... & d_{n-1}/d_{n-2} & b_{2n} \\
a_{n1} & a_{n2}&... & a_{n-1,n} & a_{nn} \end{array}\right) .$

Using the condition that all $latex d_{1},...,d_{n-1}$ are different from zero, we can make zero the elements $latex a_{n1}, ..., a_{n-1,n}$. The result is:

$latex B=\left(\begin{array}{ccccc}d_{1} & b_{12} & ... & b_{1n} & b_{1n} \\
0 & d_{2}/d_{1} & ... & b_{2n} & b_{2n} \\... & ... & ... & ... & ... \\0 & 0 & ... & d_{n-1}/d_{n-2} & b_{2n} \\
0 & 0 & ... & 0 & b_{nn}\end{array}\right) .$

The determinant of a triangular matrix equals the product of diagonal elements because of the cross-out rule:

(1) $latex \det B=d_{1}(d_{2}/d_{1})...(d_{n-1}/d_{n-2})b_{nn}=d_{n-1}b_{nn}$

(for example, if a product contains $latex b_{1n}$, you should cross out the first row and then the product should contain one of the zeros below $latex d_1$).

On the other hand, $latex B$ is a result of premultiplication by elementary matrices: $latex B=C_{1}...C_{n-1}A$ where by Exercise 1 $latex \det C_{i}=1$ for all $latex i. $ Hence,

(2) $latex \det B=\det A=d_{n}.$

Combining (1) and (2) we get $latex b_{nn}=d_{n}/d_{n-1},$ which concludes the inductive argument.

Elementary transformations

Here we look at matrix representations of transformations called elementary.

Exercise 1. Let $latex e_{i}$ denote the $latex i$-th unit row vector and let $latex A$ be an arbitrary matrix. Then

a) premultiplication of $latex A$ by $latex e_{j}$ cuts out of $latex A$ the $latex j$-th row $latex A_{j}.$

b) Premultiplication of $latex A$ by $latex e_{i}^{T}e_{j}$ puts the row $latex A_{j}$ into the $latex i$-th row of the null matrix.

c) Premultiplication of $latex A$ by $latex I+ce_{i}^{T}e_{j}$ adds row $latex A_{j}$ multiplied by $latex c$ to row $latex A_{i},$ without changing the other rows of $latex A.$

d) The matrix $latex I+ce_{i}^{T}e_{j}$ has determinant 1.

Proof. a) It's easy to see that

$latex e_{j}A=\left( 0...0~1~0...0\right) \left(\begin{array}{ccc}a_{11} & ... & a_{1n} \\
... & ... & ... \\a_{j1} & ... & a_{jn} \\... & ... & ... \\a_{n1} & ... & a_{nn}\end{array}
\right) =\left(\begin{array}{ccc}a_{j1} & ... & a_{jn}\end{array}\right) =A_{j}.$

b) Obviously,

$latex e_{i}^{T}e_{j}A=\left(\begin{array}{c}0 \\... \\0 \\1 \\0 \\... \\0\end{array}
\right) \left(\begin{array}{ccc}a_{j1} & ... & a_{jn}\end{array}
\right) =\left(\begin{array}{ccc}0 & ... & 0 \\... & ... & ... \\a_{j1} & ... & a_{jn} \\... & ... & ... \\
0 & ... & 0\end{array}
\right) =\left(\begin{array}{c}\Theta \\A_{j} \\\Theta\end{array}
\right) $

($latex A_{j}$ in the $latex i$-th row, $latex \Theta$ denotes null matrices of conformable dimensions)

c) $latex (I+ce_{i}^{T}e_{j})A=A+ce_{i}^{T}e_{j}A=\left(\begin{array}{c}
A_{1} \\... \\A_{i} \\... \\A_{n}\end{array}
\right) +\left(\begin{array}{c}\Theta \\... \\cA_{j} \\... \\\Theta\end{array}
\right) =\left(\begin{array}{c}A_{1} \\... \\A_{i}+cA_{j} \\
... \\A_{n}\end{array}\right) .$

d) The matrix $latex A=I+ce_{i}^{T}e_{j}$ has ones on the main diagonal and only one nonzero element $latex a_{ij}=c$ outside it. By the Leibniz formula it's determinant is 1.

The reader can easily solve the next

Exercise 2. a) Postmultiplication of $latex A$ by $latex e_{j}^{T}$ cuts out of $latex A$ the $latex j$-th column $latex A^{(j)}.$

b) Postmultiplication of $latex A$ by $latex e_{j}^{T}e_{i}$ puts the column $latex A^{(j)}$ into the $latex i$-th column of the null matrix.

c) Postmultiplication of $latex A$ by $latex I+ce_{j}^{T}e_{i}$ adds column $latex A^{(j)}$ multiplied by $latex c$ to column $latex A^{(i)},$ without changing the other columns of $latex A.$

d) The matrix $latex I+ce_{j}^{T}e_{i}=(I+ce_{i}^{T}e_{j})^{T}$ has determinant 1.

Exercise 3. a) Premultiplication of $latex A$ by

(1) $latex \left(\begin{array}{c}e_{1} \\... \\e_{j} \\... \\e_{i} \\... \\e_{n}\end{array}
\right) $

permutes rows $latex A_{i},A_{j}.$

b) Postmultiplication of $latex A$ by the transpose of (1) permutes columns $latex A^{(i)},A^{(j)}.$

This is a general property of permutation matrices. Recall also that their determinants can be only $latex \pm 1.$

Definition. 1) Adding some row multiplied by a constant to another row or 2) adding some column multiplied by a constant to another column or 3) permuting rows or columns is called an elementary operation. Accordingly, matrices that realize them are called elementary matrices.

Main theorem: Jordan normal form

By Exercise 1, it is sufficient to show that in each root subspace the matrix takes the Jordan form.

Step 1. Take a basis

(1) $latex x_{1,p},...,x_{k,p}\in N_{\lambda }^{(p)}$ independent relative to $latex N_{\lambda }^{(p-1)}.$

Consecutively define

(2) $latex x_{1,p-1}=(A-\lambda I)x_{1,p},\ ...,\ x_{k,p-1}=(A-\lambda I)x_{k,p}\in N_{\lambda }^{(p-1)},$

...

(3) $latex x_{1,1}=(A-\lambda I)x_{1,2},\ ...,\ x_{k,1}=(A-\lambda I)x_{k,2}\in N_{\lambda }^{(1)}.$

Exercise 1. The vectors in (2) are linearly independent relative to $latex N_{\lambda }^{(p-2)},...,$ the vectors in (3) are linearly independent.

Proof. Consider (2), for example. Suppose that $latex \sum_{j=1}^{k}a_{j}x_{j,p-1} \in N_{\lambda }^{(p-2)}.$ Then

$latex 0=(A-\lambda I)^{p-2}\sum_{j=1}^{k}a_{j}x_{j,p-1}=(A-\lambda I)^{p-1}\sum_{j=1}^{k}a_{j}x_{j,p}.$

The conclusion that $latex \sum_{j=1}^{k}a_{j}x_{j,p}\in N_{\lambda}^{(p-1)} $ contradicts assumption (1).

Exercise 2. The system of $latex kp$ vectors listed in (1)-(3) is linearly independent, so that its span $latex L_{x}$ is of dimension $latex kp.$

Proof. Suppose $latex \sum_{j=1}^{k}a_{j,p}x_{j,p}+...+\sum_{j=1}^{k}a_{j,1}x_{j,1}=0.$ Then by inclusion relations

$latex \sum_{j=1}^{k}a_{j,p}x_{j,p}=-\sum_{j=1}^{k}a_{j,p-1}x_{j,p-1}-...-
\sum_{j=1}^{k}a_{j,1}x_{j,1}\in N_{\lambda }^{(p-1)}$

which implies $latex a_{j,p}=0$ for $latex j=1,...,k,$ by relative independence stated in (1). This process can be continued by Exercise 1 to show that all coefficients are zeros.

Next we show that in each of $latex N_{\lambda }^{(p)},...,N_{\lambda}^{(1)} $ we can find a basis relative to the lower indexed subspace $latex N_{\lambda }^{(p-1)},...,N_{\lambda }^{(0)}=\{0\}.$ According to (1), in $latex N_{\lambda }^{(p)}$ we already have such a basis. If the vectors in (2) constitute such a basis in $latex N_{\lambda }^{(p-1)}$, we consider $latex N_{\lambda }^{(p-2)}.$

Step 2. If not, by Exercise 3 we can find vectors

$latex y_{1,p-1},...,y_{l,p-1}\in N_{\lambda }^{(p-1)}$

such that

$latex x_{1,p-1},...,x_{k,p-1},y_{1,p-1},...,y_{l,p-1}$ represent a basis relative to $latex N_{\lambda }^{(p-2)}.$

Then we can define

$latex y_{1,p-2}=(A-\lambda I)y_{1,p-1},\ ...,\ y_{l,p-2}=(A-\lambda I)y_{l,p-1}\in N_{\lambda }^{(p-2)},$

...

$latex y_{1,1}=(A-\lambda I)y_{1,2},\ ...,\ y_{l,1}=(A-\lambda I)y_{l,2}\in N_{\lambda }^{(1)}.$

By Exercise 2, the $latex y$'s defined here are linearly independent. But we can show more:

Exercise 3. All $latex x$'s from Step 1 combined with the $latex y$'s from Step 2 are linearly independent.

The proof is analogous to that of Exercise 2.

Denote $latex L_{y}$ the span of vectors introduced in Step 2. $latex L_{x}\cap L_{y}=\{0\}$ because they have different bases. Therefore we can consider a direct sum $latex L_{x}\dotplus L_{y}.$ Repeating Step 2 as many times as necessary, after the last step we obtain a subspace, say, $latex L_{z},$ such that $latex N_{\lambda }^{(p)}=L_{x} \dotplus L_{y} \dotplus ... \dotplus L_{z}.$ The restrictions of $latex A$ onto the subspaces on the right is described by Jordan cells with the same $latex \lambda $ and of possibly different dimensions. We have proved the following theorem:

Theorem (Jordan form) For a matrix $latex A$ in $latex C^{n}$ one can find a basis in which $latex A$ can be written as a block-diagonal matrix

(1) $latex A=\left(\begin{array}{ccc}A_{1} & ... & ... \\... & ... & ... \\... & ... & A_{m}\end{array}\right) .$

Here $latex A_{i}$ are (square) Jordan cells, with possibly different lambdas on the main diagonal and of possibly different sizes, and all off-diagonal blocks are zero matrices of compatible dimensions.

Playing with bases

Here is one last push before the main result. Exercise 1 is one of the basic facts about bases.

Exercise 1. In $latex C^{n}$ any system of $latex k<n$ linearly independent vectors $latex x_{1},...,x_{k}$ can be completed to form a basis.

Proof. Let $latex e_{1},...,e_{n}$ be a basis in $latex C^{n}.$ If each of $latex e_{1},...,e_{n}$ belongs to $latex span(x_{1},...,x_{k}),$ then by the lemma we would have $latex n\leq k,$ contradicting the assumption $latex k<n.$ Hence, among $latex e_{1},...,e_{n}$ there is at least on vector that does not belong to $latex span(x_{1},...,x_{k}).$ We can add it to $latex x_{1},...,x_{k}$ denoting it $latex x_{k+1}.$

Suppose $latex \sum_{j=1}^{k+1}a_{j}x_{j}=0.$ Since $latex x_{k+1}$ is independent of the other vectors, we have $latex a_{k+1}=0$ but then because of independence of $latex x_{1},...,x_{k}$ all other coefficients are zero. Thus, $latex x_{1},...,x_{k},x_{k+1}$ are linearly independent.

If $latex k+1<n,$ we can repeat the addition process, until we obtain $latex n$ linearly independent vectors $latex x_{1},...,x_{n}.$ By construction, $latex e_{1},...,e_{n}$ belong to $latex span(x_{1},...,x_{n}).$ Since $latex e_{1},...,e_{n}$ span $latex C^{n},$ $latex x_{1},...,x_{n}$ do too and therefore form a basis.

Definition 1. Let $latex L_{1}\subset L_{2}$ be two subspaces. Vectors $latex x_{1},...,x_{m}\in L_{2}$ are called linearly independent relative to $latex L_{1}$ if any nontrivial linear combination $latex \sum a_{j}x_{j}$ does not belong to $latex
L_{1}.$ For the purposes of this definition, it is convenient to denote by $latex \Theta $ a generic element of $latex L_{1}.$ $latex \Theta $ plays the role of zero and the definition looks similar to usual linear independence: $latex \sum
a_{j}x_{j}\neq \Theta $ for any nonzero vector $latex a.$ Rejecting this definition, we can say that $latex x_{1},...,x_{m}\in L_{2}$ are called linearly dependent relative to $latex L_{1}$ if $latex \sum a_{j}x_{j}=\Theta $ for some nonzero vector $latex a.$

Definition 2. Let $latex L_{1}\subset L_{2}$ be two subspaces. Vectors $latex x_{1},...,x_{m}\in L_{2}$ are called a basis relative to $latex L_{1}$ if they are linearly independent and can be completed by some basis from $latex L_{1}$ to form a basis in $latex L_{2}.$

Exercise 2. Show existence of a relative basis in $latex L_{2}.$

Proof. Take any basis in $latex L_{1}$ (say, $latex x_{1},...,x_{k}$) and, using Exercise 1, complete it by some vectors (say, $latex x_{k+1},...,x_{n}\in L_{2}$) to get a basis in $latex L_{2}.$ Then, obviously, $latex x_{k+1},...,x_{n}$ form a basis in $latex L_{2}$ relative to $latex L_{1}.$ Besides, none of $latex x_{k+1},...,x_{n}$ belongs to $latex L_{1}.$

Exercise 3. Any system of vectors $latex x_{1},...,x_{k}\in L_{2}$ linearly independent relative to $latex L_{1}$ can be completed to form a relative basis in $latex L_{2}.$

Proof. Take a basis in $latex L_{1}$ (say, $latex x_{k+1},...,x_{l}$) and add it to $latex x_{1},...,x_{k}.$ The resulting system $latex x_{1},...,x_{k},x_{k+1},...,x_{l}$ is linearly independent. Indeed, if $latex \sum_{j=1}^{l}a_{j}x_{j}=0,$ then

$latex \sum_{j=1}^{k}a_{j}x_{j}=-\sum_{j=k+1}^{l}a_{j}x_{j}\in L_{1}.$

By assumption of relative linear independence $latex a_{1}=...=a_{k}=0$ but then the remaining coefficients are also zero.

By Exercise 1 we can find $latex x_{l+1},...,x_{n}$ such that $latex x_{1},...,x_{k},x_{k+1},...,x_{l},x_{l+1},...,x_{n}$ is a basis in $latex L_{2}.$ Now the system $latex x_{1},...,x_{k},x_{l+1},...,x_{n}$ is a relative basis because these vectors are linearly independent and together with $latex x_{k+1},...,x_{l}\in L_{1}$ form a basis in $latex L_{2}.$

Chipping off root subspaces

The basis in which a matrix is diagonal consists of eigenvectors. Therefore if the number of linearly independent eigenvectors is less than $latex n,$ such a matrix cannot be diagonalized.

The general result we are heading to is that any matrix in $latex C^{n}$ in an appropriately chosen basis can be written as a block-diagonal matrix

(1) $latex A=\left(\begin{array}{ccc}A_{1} & ... & ... \\
... & ... & ... \\... & ... & A_{m}\end{array}\right) .$

Here $latex A_{i}$ are Jordan cells, with possibly different lambdas on the main diagonal and of possibly different sizes, and all off-diagonal blocks are zero matrices of compatible dimensions. The next exercise is an intermediate step towards that result.

Exercise 1. Let $latex A$ have $latex k$ different eigenvalues $latex \lambda_1,...,\lambda_k.$ Then $latex C^n$ can be represented as a direct sum of $latex k$ invariant subspaces

(2) $latex C^n=N_{\lambda_1}^{(p_1)} \dotplus ... \dotplus N_{\lambda_k}^{(p_k)}.$

The subspace $latex N_{\lambda_i}^{(p_i)}$ consists of only root vectors belonging to the eigenvalue $latex \lambda_i.$

Proof. By Exercise 2 we have $latex C^n=N_{\lambda_1}^{(p_1)}\dotplus L_1$ where the subspace $latex L_1$ has two properties: it is invariant with respect to $latex A$ and the restriction of $latex A$ to $latex L_1$ does not have $latex \lambda_1$ as an eigenvalue. $latex N_{\lambda_1}^{(p_1)}$ consists of root vectors belonging to $latex \lambda_1.$ Applying Exercise 2 to $latex L_1$ we get $latex L_1=N_{\lambda_2}^{(p_2)}\dotplus L_2$ where $latex N_{\lambda_2}^{(p_2)},L_{2}$ have similar properties. Applying Exercise 2 $latex k$ times we finish the proof.

Note that the restriction of $latex A$ onto $latex N_{\lambda_i}^{(p_i)}$ may not be described by a single Jordan cell. A matrix may have more than one Jordan cell with the same eigenvalue. To make this point clearer, note that the matrices

$latex \left(\begin{array}{cccc}\lambda & 1 & 0 & 0 \\
0 & \lambda & 0 & 0 \\0 & 0 & \lambda & 1 \\0 & 0 & 0 & \lambda\end{array}
\right) $   and   $latex \left(\begin{array}{cccc}\lambda & 1 & 0 & 0 \\
0 & \lambda & 1 & 0 \\0 & 0 & \lambda & 1 \\0 & 0 & 0 & \lambda\end{array}\right) $

are not the same (the first matrix has two Jordan cells on the main diagonal and the second one is itself a Jordan cell). It will take some effort to get from (2) to (1).

Exercise 4. Show that for the matrix from Exercise 3 $latex \det (A-\lambda _{1}I)=\left(\lambda -\lambda _{1}\right) ^p$ ($latex \lambda _{1}$ - any number).

Exercise 5. In addition to Exercise 4, show that in $latex N_{\lambda }^{(p)}$ the matrix $latex A$ has only one eigenvector, up to a scaling factor. Hint: use the Jordan cell.

Action of a matrix in its root subspace

The purpose of the following discussion is to reveal the matrix form of $latex A$ in $latex N_{\lambda }^{(p)}.$

Definition 1. Nonzero elements of $latex N_{\lambda }^{(p)}$ are called root vectors. This definition can be detailed as follows:

Elements of $latex N_{\lambda }^{(1)}\setminus {0}$ are eigenvalues.

Elements of $latex N_{\lambda }^{(2)}\setminus N_{\lambda }^{(1)}$ are called root vectors of 1st order.

...

Elements of $latex N_{\lambda }^{(p)}\setminus N_{\lambda }^{(p-1)}$ are called root vectors of order $latex p-1$.

Thus, root vectors belong to

$latex N_\lambda^{(p)} \setminus{0}=\left( N_\lambda^{(p)} \setminus N_\lambda^{(p-1)} \right) \cup ... \cup \left( N_\lambda^{(2)} \setminus N_\lambda^{(1)}\right) \cup \left( N_\lambda^{(1)} \setminus {0} \right)$

where the sets of root vectors of different orders do not intersect.

Exercise 1. $latex (A-\lambda I)\left( N_{\lambda }^{(k)}\setminus N_{\lambda }^{(k-1)}\right) \subset \left( N_{\lambda }^{(k-1)}\setminus N_{\lambda}^{(k-2)}\right) .$

Proof. Suppose $latex x\in N_{\lambda }^{(k)}\setminus N_{\lambda }^{(k-1)},$ that is, $latex (A-\lambda I)^{k}x=0$ and $latex (A-\lambda I)^{k-1}x\neq 0.$ Denoting $latex y=(A-\lambda I)x,$ we have $latex (A-\lambda I)^{k-1}y=0$ and $latex (A-\lambda I)^{k-2}y\neq 0,$ which means that $latex y\in N_{\lambda }^{(k-1)}\setminus N_{\lambda }^{(k-2)}$ and $latex A-\lambda I$ maps $latex N_{\lambda }^{(k)}\setminus N_{\lambda }^{(k-1)}$ into $latex N_{\lambda }^{(k-1)}\setminus N_{\lambda}^{(k-2)}.$

Now, starting from some $latex x_{p}\in N_{\lambda }^{(p)}\setminus N_{\lambda}^{(p-1)},$ we extend a chain of root vectors all the way to an eigenvector. By Exercise 1, the vector $latex x_{p-1}=(A-\lambda I)x_{p}$ belongs to $latex N_{\lambda }^{(p-1)}\setminus N_{\lambda }^{(p-2)}.$ From the definition of $latex x_{p-1}$ we see that

(1) $latex Ax_{p}=\lambda x_{p}+x_{p-1},$   $latex x_{p-1}\in N_{\lambda}^{(p-1)}\setminus N_{\lambda }^{(p-2)}$

($latex x_{p}$ is an "eigenvector" up to a root vector of lower order). Similarly, denoting $latex x_{p-2}=(A-\lambda I)x_{p-1},$ we have

(2) $latex Ax_{p-1}=\lambda x_{p-1}+x_{p-2},$   $latex x_{p-2}\in N_{\lambda}^{(p-2)}\setminus N_{\lambda }^{(p-3)}.$

...

Continuing in the same way, we get $latex x_{1}=(A-\lambda I)x_{2}\in N_{\lambda}^{(1)}\setminus {0},$

(3) $latex Ax_{2}=\lambda x_{2}+x_{1},$   $latex x_{1}\in N_{\lambda}^{(1)}\setminus {0},$

(4) $latex Ax_{1}=\lambda x_{1},$   $latex x_{1}\neq 0.$

Exercise 2. The vectors $latex x_{1},...,x_{p}$ defined above are linearly independent.

Proof. If $latex \sum_{j=1}^{p}a_{j}x_{j}=0,$ then $latex a_{p}x_{p}=-\sum_{j=1}^{p-1}a_{j}x_{j}.$ Here the left side belongs to $latex N_{\lambda}^{(p)}\setminus N_{\lambda }^{(p-1)}$ and the right side belongs to $latex N_{\lambda }^{(p-1)}$ because of inclusion relations. Hence, $latex a_{p}=0.$ Similarly, all other coefficients are zero.

By Exercise 2, the vectors $latex x_{1},...,x_{p}$ form a basis in $latex L=span(x_{1},...,x_{p}).$

Exercise 3. The transformation $latex A$ in $latex L$ is given by the matrix

(5) $latex A=\left(\begin{array}{ccccc}\lambda & 1 & 0 & ... & 0 \\0 & \lambda & 1 & ... & 0 \\
... & ... & ... & ... & ... \\0 & 0 & 0 & ... & 1 \\v\\0 & 0 & 0 & ... & \lambda\end{array}
\right) =\lambda I+J$

where $latex J$ is a matrix with unities in the first superdiagonal and zeros everywhere else.

Proof. Since $latex x_{1},...,x_{p}$ is taken as the basis, $latex x_{i}$ can be identified with the unit column-vector $latex e_{i}.$ The equations (1)-(4) take the form

$latex Ae_{1}=\lambda e_{1},$ $latex Ae_{j}=\lambda e_{j}+e_{j-1},$ $latex j=2,...,p.$

Putting these equations side by side we get

$latex AI=A\left( e_{1},...,e_{p}\right) =\left( Ae_{1},...,Ae_{p}\right) =\left(\lambda e_{1},\lambda e_{2}+e_{1},...,\lambda e_{p}+e_{p-1}\right) =$

=$latex \left(\begin{array}{cccc}\lambda & 1 & ... & 0 \\0 & \lambda & ... & 0 \\
... & ... & ... & ... \\0 & 0 & ... & 1 \\0 & 0 & ... & \lambda\end{array}\right) .$

Definition 2. The matrix in (5) is called a Jordan cell.

Properties of root subspaces

Let $latex A$ be a square matrix and let $latex \lambda \in \sigma (A)$ be its eigenvalue. As we know, the nonzero elements of the null space $latex N(A-\lambda I)=\{x:(A-\lambda I)x=0\}$ are the corresponding eigenvectors. This definition is generalized as follows.

Definition 1. The subspaces $latex N_{\lambda }^{(k)}=N((A-\lambda I)^{k}),$ $latex k=1,2,...$ are called root subspaces of $latex A$ corresponding to $latex \lambda .$

Exercise 1. a) Root subspaces are increasing:

(1) $latex N_{\lambda }^{(k)}\subset N_{\lambda }^{(k+1)}$ for all $latex k\geq 1$

and b) there is such $latex p\leq n$ that all inclusions (1) are strict for $latex k<p$ and

(2) $latex N_{\lambda }^{(p)}=N_{\lambda }^{(p+1)}=...$

Proof. a) If $latex x\in N_{\lambda }^{(k)}$ for some $latex k,$ then $latex (A-\lambda I)^{k+1}x=(A-\lambda I)(A-\lambda I)^{k}x=0,$ which shows that $latex x\in N_{\lambda }^{(k+1)}.$

b) (1) implies $latex \dim N_{\lambda }^{(k)}\leq \dim N_{\lambda }^{(k+1)}.$ Since all root subspaces are contained in $latex C^{n},$ there are $latex k$ such that $latex N_{\lambda }^{(k)}=N_{\lambda }^{(k+1)}.$ Let $latex p$ be the smallest such $latex k.$ Then all inclusions (1) are strict for $latex k<p.$

Suppose $latex N_{\lambda}^{(k+1)}\setminus N_{\lambda }^{(k)}\neq \varnothing $ for some $latex k\ge p.$ Then there exists $latex x\in N_{\lambda }^{(k+1)}$ such that $latex x\notin N_{\lambda}^{(k)}$, that is, $latex (A-\lambda I)^{k+1}x=0,$ $latex (A-\lambda I)^{k}x\neq 0.$ Put $latex y=(A-\lambda I)^{k-p}x.$ Then $latex (A-\lambda I)^{p+1}y=(A-\lambda I)^{k+1}x=0,$ $latex (A-\lambda I)^{p}y=(A-\lambda I)^{k}x\notin 0.$ This means
that $latex y\in N_{\lambda }^{(p+1)}\setminus N_{\lambda }^{(p)}$ which contradicts the definition of $latex p.$

Definition 2. Property (2) can be called stabilization. The number $latex p$ from (2) is called a height of the eigenvalue $latex \lambda$.

Exercise 2. Let $latex \lambda \in \sigma (A)$ and let $latex p$ be the number from Exercise 1. Then

(3) $latex C^{n}=N_{\lambda }^{(p)}\dotplus \text{Img}[(A-\lambda I)^{p}].$

Proof. By the rank-nullity theorem applied to $latex (A-\lambda I)^{p}$ we have $latex n=\dim N_{\lambda }^{(p)}+\dim \text{Img}[(A-\lambda I)^{p}].$ By Exercise 3, to prove (3) it is sufficient to establish that $latex L\equiv N_{\lambda}^{(p)}\cap \text{Img}[(A-\lambda I)^{p}]=\{0\}.$ Let's assume that $latex L$ contains a nonzero vector $latex x.$ Then we have $latex x=(A-\lambda I)^{p}y$ for some $latex y.$ We obtain two facts:

$latex (A-\lambda I)^{p}y\neq 0$ $latex \Longrightarrow y\notin N_{\lambda }^{(p)},$

$latex (A-\lambda I)^{2p}y=(A-\lambda I)^{p}(A-\lambda I)^{p}y=(A-\lambda I)^{p}x=0\Longrightarrow y\in N_{\lambda }^{(2p)}.$

It follows that $latex y$ is a nonzero element of $latex N_{\lambda }^{(2p)}\setminus N_{\lambda }^{(p)}.$ This contradicts (2). Hence, the assumption $latex L\neq \{0\} $ is wrong, and (3) follows.

Exercise 3. Both subspaces at the right of (3) are invariant with respect to $latex A.$

Proof. If $latex x\in N_{\lambda }^{(p)},$ then by commutativity of $latex A$ and $latex A-\lambda I$ we have $latex (A-\lambda I)^{p}Ax=A(A-\lambda I)^{p}x=0,$ so $latex Ax\in N_{\lambda }^{(p)}.$

Suppose $latex x\in \text{Img}[(A-\lambda I)^{p}],$ so that $latex x=(A-\lambda I)^{p}y$ for some $latex y.$ Then $latex Ax=(A-\lambda I)^{p}Ay\in \text{Img}[(A-\lambda I)^{p}].$

Exercise 3 means that, for the purpose of further analyzing $latex A,$ we can consider its restrictions onto $latex N_{\lambda }^{(p)}$ and $latex \text{Img}[(A-\lambda I)^{p}].$

Exercise 4. The restriction of $latex A$ onto $latex N_{\lambda }^{(p)}$ does not have eigenvalues other than $latex \lambda .$

Proof. Suppose $latex Ax=\mu x,$ $latex x\neq 0,$ for some $latex \mu .$ Since $latex x\in N_{\lambda }^{(p)},$ we have $latex (A-\lambda I)^{p}x=0.$ Then $latex (A-\lambda I)x=(\mu -\lambda )x$ and $latex 0=(A-\lambda I)^{p}x=(\mu -\lambda )^{p}x$. This implies $latex \mu =\lambda .$

Exercise 5. The restriction of $latex A$ onto $latex \text{Img}[(A-\lambda I)^{p}]$ does not have $latex \lambda $ as an eigenvalue (so that $latex A-\lambda I$ is invertible).

Proof. Suppose $latex x\in \text{Img}[(A-\lambda I)^{p}]$ and $latex Ax=\lambda x,$ $latex
x\neq 0.$ Then $latex x=(A-\lambda I)^{p}y$ for some $latex y\neq 0$ and $latex 0=(A-\lambda
I)x=(A-\lambda I)^{p+1}y.$ By Exercise 1 $latex y\in N_{\lambda }^{(p+1)}=N_{\lambda }^{(p)}$ and $latex x=(A-\lambda I)^{p}y=0.$ This contradicts the choice of $latex x.$