A predator-prey model. Let \(x_n\) and \(y_n\) be the number of owls and mice, respectively, at the end of year \(n\). Suppose that the change in population from one year to the next is modelled by \({\bf v}_{n+1}=M{\bf v}_n\), where \({\bf v}_n\) is the column vector with entries \(x_n\) and \(y_n\), and \[M=\left(\begin{matrix} 0.6 & 0.4 \\ -0.1 & 1.2 \end{matrix}\right).\] So given a starting population \({\bf v}_0\), the population after \(n\) years is \(M^n{\bf v}_0\). Can we get a formula for \(M^n\)? In this simple case, we could guess one by trial and error, but for larger matrices that is not feasible. However, if we can construct a change of basis to a diagonal form \[N = P^{-1} M P = \begin{pmatrix} a & 0\\ 0& b\end{pmatrix}\] for some \(a,b\in\mathbb{R}\) and invertible \(P\in M_{2\times 2}(\mathbb{R})\) then the problem becomes very easy to solve \[M^n = (PNP^{-1})^n = P N^n P^{-1} = P\begin{pmatrix} a^n & 0\\ 0& b^n\end{pmatrix} P^{-1}\,.\] So the idea is to solve the original problem by changing basis so that \(M\) is diagonal. This process is called diagonalization, and almost all square matrices can be diagonalized.

Consider the following system of ordinary differential equations for \(x(t)\) and \(y(t)\): \[\begin{aligned} \frac{dx}{dt} & = -x+4y, \\ \frac{dy}{dt} & = -2x+5y. \end{aligned}\] This can be written in matrix form as \[\frac{d}{dt} {\bf v}= M {\bf v},\] where \[{\bf v}(t) = \begin{pmatrix} x(t)\\y(t) \end{pmatrix} \qquad\text{and}\qquad M=\left(\begin{matrix} -1 & 4 \\ -2 & 5 \end{matrix}\right).\] Now let’s assume that via some change of basis \(P\) we can make \(M\) diagonal with diagonal entries 1 and 3 (this is true in this case, as we will see in example [ex:diagonalization-1] below) \[N = P^{-1}MP = \begin{pmatrix}1&0\\0&3\end{pmatrix}\, .\] Then the differential equation can be written as \[\frac{d}{dt} {\bf v}= PNP^{-1} {\bf v},\] or equivalently (taking into account that \(P\) is a constant and that derivatives are linear) \[\frac{d}{dt}(P^{-1}{\bf v}) = N (P^{-1}{\bf v})\, .\] So if we define \[\begin{pmatrix} \tilde x\\ \tilde y \end{pmatrix} \mathrel{\mathop:}\mathrel{\mkern-1.2mu}=P^{-1}{\bf v}\] we have the much simpler system \[\begin{aligned} \frac{d\tilde x}{dt} & = \tilde x\\ \frac{d\tilde y}{dt} & = 3\tilde y \end{aligned}\] with solution \(x(t)=C e^{t}\) and \(y(t)=De^{3t}\). Therefore \[\begin{pmatrix}x(t)\\y(t)\end{pmatrix} = P\begin{pmatrix}C e^{t}\\De^{3t}\end{pmatrix}\, .\]

If \(A\) is a diagonal matrix, then the eigenvalues of \(A\) are precisely the entries on the diagonal. For example, \[A=\left(\begin{matrix} -2 & 0 & 0 \\ 0 & 3 & 0 \\ 0 & 0 & 1 \end{matrix}\right).\] has characteristic polynomial \(p_A(t)=-(t+2)(t-3)(t-1)\), and so the eigenvalues are \(\lambda=-2,\,3,\,1\).

If \(A\) is an upper triangular matrix, then the eigenvalues of \(A\) are again the entries on the diagonal. For example \[A=\left(\begin{matrix} -2 & 5 & 1 \\ 0 & 3 & 2 \\ 0 & 0 & 1 \end{matrix}\right)\] has characteristic polynomial \(p_A(t)=-(t+2)(t-3)(t-1)\), and so the eigenvalues are \(\lambda=-2,\,3,\,1\), as before.

Find the eigenvalues of the matrix \[A=\left(\begin{matrix} 0 & 1 \\ 1 & 0 \end{matrix}\right).\] Solution. The characteristic polynomial is \(p_A(t)=t^2-1\), and so the eigenvalues are \(\lambda=\pm1\).

Find the eigenvalues of the matrix \[A=\left(\begin{matrix} -2 & 1 & 2 \\ 2 & 3 & -4 \\ -1 & 1 & 1 \end{matrix}\right).\] Solution. We calculate \[\begin{aligned} p_A(t) & = \det(A-tI ) \\ & = \det\left(\begin{matrix} -2-t & 1 & 2 \\ 2 & 3-t & -4 \\ -1 & 1 & 1-t \end{matrix}\right) \\ & = (-2-t)(3-t)(1-t)+4+4+4(-2-t)+2(3-t)-2(1-t) \\ & = -t^3+2t^2+t-2 \\ & = -(t-2)(t-1)(t+1). \end{aligned}\] The factorization is obtained, for example, by spotting that \(t=1\) is a root, and then doing long division by the factor \(t-1\). The eigenvalues are \(\lambda=2,\,1,\,-1\).

The eigenvectors in example [example1-1] are clearly \({\bf v}_1=(1,0,0)\), \({\bf v}_2=(0,1,0)\) and \({\bf v}_3=(0,0,1)\).

The eigenvectors in example [example1-2] are \({\bf v}_1=(1,0,0)\), \({\bf v}_2=(1,1,0)\) and \({\bf v}_3=(-4/3,-1,1)\).

The eigenvectors in example [example1-3] are \({\bf v}_1=(1,1)\) and \({\bf v}_2=(1,-1)\).

The eigenvectors in example [example1-4] are \({\bf v}_1=(1,2,1)\), \({\bf v}_2=(1,1,1)\) and \({\bf v}_3=(2,0,1)\).

If an eigenvalue \(\lambda\) has multiplicity \(k\neq 0 \in \mathbb{N}\) it means that the characteristic polynomial takes the form \[p_A(t) = \left( t - \lambda\right)^k\, Q(t)\,,\] where the polynomial \(Q(t)\) has degree \(N-k\) and it is non-vanishing on \(\lambda\), i.e. \(Q(\lambda) \neq 0\).

The \(2\times2\) matrix \(A=I\) has eigenvalue \(\lambda=1\) (twice), and two independent eigenvectors: the eigenspace is 2-dimensional.

By contrast, \[A=\left(\begin{matrix} 1 & 1 \\ 0 & 1 \end{matrix}\right)\] also has eigenvalue \(\lambda=1\) (twice), but \({\bf v}=(1,0)\) is the only eigenvector (up to scalar multiplication): the eigenspace is 1-dimensional, namely \(\mathop{\mathrm{span}}({\bf v})\).

Consider the matrices \[A=\left(\begin{matrix}1 && 0\\ 0 && 1\end{matrix}\right)=I\,, \qquad B=\left(\begin{matrix}1 && \alpha\\ 0 && 1\end{matrix}\right)\] with \(\alpha\in \mathbb{R}\) and \(\alpha \neq 0\). Clearly \(p_A(t) = p_B(t) = (t-1)^2\) so \(A\) and \(B\) have eigenvalues \(\lambda=\{1,1\}\). Despite having the same eigenvalues \(A\) cannot possibly be similar to \(B\), in fact all the matrices similar to \(A\) are given by the equivalence class \(\left[A\right] = \{ I \}\) so \(B \notin [A]\) which means that \(B\) is not similar to \(A\).

As we will see later on, eigenvalues corresponding to different eigenvectors will be automatically linearly independent, this means that each eigenspace \(V_\lambda\) will be linearly independent from \(V_\mu\) when the eigenvalues \(\lambda\) is different from the eigenvalue \(\mu\).

In particular, we know that \(1\leq \dim\, V_\lambda \leq m_\lambda\), where \(m_\lambda\) is the algebraic multiplicity of the eigenvalue \(\lambda\). Since the degree of the characteristic polynomial is precisely the dimension \(n\) of our matrix, it means that if we sum the multiplicities of all the eigenvalues we find \(\sum_\lambda m_\lambda = n\).

Hence, for the matrix under consideration to be diagonalizable, we must have for all the eigenspaces \(V_\lambda\) that \(\dim V_\lambda = m_\lambda\), since only in this case we will have a set of \(n\) linearly independent eigenvectors. We can equivalently say (using definition [def:geometric-multiplicity]) that a matrix will be diagonalizable if and only if the geometric and algebraic multiplicities of all eigenvalues are the same.

If possible, diagonalize the matrix \[A=\left(\begin{matrix} -1 & 4 \\ -2 & 5 \end{matrix}\right).\] Solution. \(p(t)=t^2-4t+3=(t-1)(t-3)\), so the eigenvalues are \(\lambda_1=1\) and \(\lambda_2=3\).

• \(\lambda=1\) \[\left(\begin{matrix} 0 \\ 0 \end{matrix}\right)={\bf 0}=(A - I){\bf v} =\left(\begin{matrix} -2 & 4 \\ -2 & 4 \end{matrix}\right) \left(\begin{matrix} v_1 \\ v_2 \end{matrix}\right)\] gives the condition \(-2v_1+4v_2=0\), so taking \(v_2=1\) gives \(v_1=2\), and \[{\bf v}_1=\left(\begin{matrix} 2 \\ 1 \end{matrix}\right).\]

• \(\lambda=3\) \[\left(\begin{matrix} 0 \\ 0 \end{matrix}\right)={\bf 0}=(A-3I){\bf v} =\left(\begin{matrix} -4 & 4 \\ -2 & 2 \end{matrix}\right) \left(\begin{matrix} v_1 \\ v_2 \end{matrix}\right)\] gives the condition \(-4v_1+4v_2=0\), so taking \(v_2=1\) gives \(v_1=1\), and so \[{\bf v}_2=\left(\begin{matrix} 1 \\ 1 \end{matrix}\right).\]

Therefore we set \[M=\left(\begin{matrix} 2 & 1 \\ 1 & 1 \end{matrix}\right),\quad M^{-1}=\left(\begin{matrix} 1 & -1 \\ -1 & 2 \end{matrix}\right),\] and then \[M^{-1}AM=\left(\begin{matrix} 1 & 0 \\ 0 & 3 \end{matrix}\right).\]

The construction in the previous example gives you \(M\); if you want to check your answer without computing \(M^{-1}\), just check that \(AM=MD\), where \(D\) is the diagonal matrix of eigenvalues (in the right order).

Solve the system of ODEs \[\begin{aligned} \dot{x} & = -x+4y, \\ \dot{y} & = -2x+5y\,, \end{aligned}\] where \(x=x(t)\,,\,y=y(t)\) and \(\dot{x} = \frac{d x(t)}{dt}\), similarly \(\dot{y} = \frac{d y(t)}{dt}\).

Solution. The procedure is to diagonalize the system, which amounts to the same thing as changing basis. If \({\bf v}\) denotes the column vector with entries \((x,y)\), put \({\bf w}=M^{-1}{\bf v}\). Then \({\bf w}(t)\) satisfies the system \(\dot{\bf w}=D{\bf w}\), where \(D={\rm{diag}}(1, 3)\). The solution is \(w_1(t)=c_1\exp(t)\), \(w_2(t)=c_2\exp(3t)\), with \(c_1\) and \(c_2\) constant; and then \({\bf v}=M{\bf w}\) gives \[\begin{aligned} x(t) & = 2c_1{\rm e}^t + c_2{\rm e}^{3t}, \\ y(t) & = c_1{\rm e}^t + c_2{\rm e}^{3t}. \end{aligned}\] (At this stage, you should substitute these answers back into the ODEs to check the calculation!)

If possible, diagonalize the matrix \[A=\left(\begin{matrix} 1 & 2 \\ 0 & 1 \end{matrix}\right).\] Solution. Here \(p(t)=(1-t)^2\), so there is one eigenvalue are \(\lambda=1\) with algebraic multiplicity \(2\). Now \[\left(\begin{matrix} 0 \\ 0 \end{matrix}\right)={\bf 0}=(A-I){\bf v} =\left(\begin{matrix} 0 & 2 \\ 0 & 0 \end{matrix}\right) \left(\begin{matrix} v_1 \\ v_2 \end{matrix}\right)\] gives \(v_2=0\). So the eigenspace \(V_1\) is spanned by \[{\bf v}_1=\left(\begin{matrix} 1 \\ 0 \end{matrix}\right).\] In other words, \(V_1\) is 1-dimensional. In view of our theorem, we conclude that \(A\) is not diagonalizable.

As mentioned before, from the above proposition we deduce that eigenspaces corresponding to different eigenvalues must be linearly independent. Since we know that the dimension of each eigenspace, \(V_\lambda\), is bounded by the algebraic multiplicity, \(m_\lambda\), of that particular eigenvalue, we deduce that the only obstruction to finding \(n\), linearly independent, eigenvectors comes from all the eigenspaces corresponding to an eigenvalue with \(m_\lambda >1\).

Given a matrix \(A\), a necessary and sufficient condition for \(A\) to be diagonalizable is that \(\dim \,V_\lambda = \dim \,\ker\left(A-\lambda I \right) = m_\lambda\), for all the eigenvalues \(\lambda\). Only in this case we can decompose the total vector space \(V\) as a direct sum of eigenspaces \[V = V_{\lambda_1} \oplus V_{\lambda_2}\oplus...\oplus V_{\lambda_p}\,,\] so that we have precisely \(n\) linearly independent eigenvectors since \[\dim V = \dim V_{\lambda_1}+ \dim V_{\lambda_2}+ ...+\dim V_{\lambda_1}=m_{\lambda_1}+m_{\lambda_2}+...+m_{\lambda_p}= n\,,\] since we know that the degree of the characteristic polynomial \(p_A(t)\) equals \(n\) and it is also equal to the sum of all the multiplicities of all the eigenvalues: \[\mbox{deg} \left(p_A(t) \right)= m_{\lambda_1}+m_{\lambda_2}+...+m_{\lambda_p}=n\,.\]

Note that the above remarks are valid only when we allow ourselves to work over the complex numbers! In particular, eigenvalues might be complex, even when the matrix is real.

Let us try to diagonalize \[A=\left(\begin{matrix} -2 & -1 \\ 5 & 2 \end{matrix}\right).\] Solution. \(p(t)=t^2+1\), so the eigenvalues are \(\lambda_1={\rm i}\) and \(\lambda_2=-{\rm i}\). Then we get \[M=\left(\begin{matrix} -2+{\rm i}& -2-{\rm i}\\ 5 & 5 \end{matrix}\right),\quad M^{-1}=\frac{1}{10} \left(\begin{matrix} -5{\rm i}& 1-2{\rm i}\\ 5{\rm i}& 1+2{\rm i}\end{matrix}\right),\] and \[M^{-1}AM=\left(\begin{matrix} {\rm i}& 0 \\ 0 & -{\rm i}\end{matrix}\right).\]

If \(A\) is a real matrix, it may be possible to diagonalize \(A\) over \({\mathbb C}\), but not over \({\mathbb R}\), as in this example. In general, we take “diagonalizable” to mean that complex numbers are allowed. But sometimes we might ask whether \(A\) is “diagonalizable when \({\mathbb R}\) is the underlying field of scalars”, or “diagonalizable over \({\mathbb R}\)”, which means that only real numbers are allowed, and is more restrictive. Note that the eigenvectors belong to \({\mathbb C}^2\), a complex vector space.

\({\mathbb C}^n\) is the vector space of \(n\)-dimensional complex vectors. The standard basis is the same as for \({\mathbb R}^n\), i.e. the \({\bf{z}}\in{\mathbb C}^n\) given by \[{\bf{z}} = \left(\begin{matrix} z_1\\ z_2\\ \vdots\\ z_n \end{matrix}\right)\] with \(z_1,...,z_n\in\mathbb{C}\) can be written as \[{\bf{z}} =z_1\,{\bf{e}}_1+z_2\,{\bf{e}}_2+...+z_n\,{\bf{e}}_n = z_1 \left(\begin{matrix} 1\\ 0\\ \vdots\\ 0 \end{matrix}\right)+z_2\left(\begin{matrix} 0\\ 1\\ 0\\ \vdots \end{matrix}\right)+...+z_n\left(\begin{matrix} 0\\ \vdots \\ 0\\ 1 \end{matrix}\right)\,.\] The only thing changing from \({\mathbb R}^n\) to \({\mathbb C}^n\) is the fact that the scalar numbers to be used are now complex numbers.

If \[A=\left(\begin{matrix} -1 & 4 \\ -2 & 5 \end{matrix}\right),\] derive a formula for \(A^n\).

Solution. Note that \(A=MDM^{-1}\), where \(M\) and \(D\) are as in example [ex:diagonalization-1]. So \[A^n=MD^nM^{-1} =\left(\begin{matrix} 2-3^n & 2\times3^n-2 \\ 1-3^n & 2\times3^n-1 \end{matrix}\right).\]

Mathematical models often lead to discrete-time evolution systems of the form \({\bf v}_{k+1}=A{\bf v}_k\). These can be solved by diagonalizing \(A\), as we did for differential equations. Sometimes we are interested in whether the solution stabilizes, ie \({\bf v}_k\to{\bf v}\) as \(k\to\infty\). Such a \({\bf v}\) has to have the property \(A{\bf v}={\bf v}\) (eigenvalue 1). Exercise for you: show that the dynamical system defined by \[A=\left(\begin{matrix} 0.8 & 0.1 \\ 0.2 & 0.9 \end{matrix}\right)\] admits a stable solution, and find it (as a unit vector).

Solution. \(p(t)=(t-0.7)(t-1)\), \({\bf v}=\pm(1,2)/\sqrt{5}\). The other eigenvector, corresponding to \(\lambda=0.7\), is \({\bf v}=\pm(1,-1)/\sqrt{2}\).

Can we define the \(k^{th}\) root of a diagonalizable matrix \(A\), i.e. a matrix \(B =\)“\(A^{1/k}\,\)”, with \(k\in \mathbb{N}\), such that \(B^k = A\) ? If \(A\) is diagonalizable, it means that \(M^{-1} A M = D= {\rm{diag}}\left(\lambda_1,...,\lambda_n\right)\) for some \(\lambda_i \in\mathbb{C}\). If we define \(B=M \tilde{D}M^{-1}\), with \(\tilde{D}={\rm{diag}}\left(\lambda_1^{1/k},...,\lambda_n^{1/k}\right)\) we can easily see that \(B^k= M{\tilde{D}}^k M^{-1}= M \,D\,M^{-1} = A\).

Note that this matrix \(B\) is not unique, for example if we take \[B_1=M {\rm{diag}}\left(\omega_1\lambda_1^{1/k},...,\omega_n\lambda_n^{1/k}\right)M^{-1},\] with \(\omega_p\) a \(k^{th}\) root of unity, i.e. \(\omega_p= e^{2\pi\,i \,p / k}\in\mathbb{C}\), \(\omega_p^k=1\), we still have \(B_1^k= A\).

\(V={\mathbb R}^n\) with the standard Euclidean inner product (dot product) \[({\bf u},{\bf v})={\bf u}\cdot{\bf v}=u_1v_1+\dots+u_nv_n.\]

\(V={\mathbb R}^n\) and \(({\bf u},{\bf v})=a_1u_1v_1+\dots+a_nu_nv_n\), where \(a_1,a_2,\ldots,a_n\) are fixed positive real numbers. This is called the weighted Euclidean inner product with weights \(a_1,\dots,a_n\). Note that symmetry and bilinearity are immediate, and positivity follows since \(a_1,\ldots,a_n>0\).

On \(V={\mathbb R}^4\), the expression \(({\bf x},{\bf y})=x_1y_1+x_2y_2+x_3y_3-x_4y_4\) is not an inner product: symmetry and bilinearity hold, but positivity does not. For example, \({\bf x}=(1,0,0,1)\) is a non-zero vector with \(({\bf x},{\bf x})=0\). However, it is of great importance: from Einstein, we know that this is the pseudo-inner product on flat space-time, with \(x_4\) being the time coordinate. The vector space \(\mathbb{R}^4\) with this pseudo-inner product is called Minkowski space.

On \(V={\mathbb R}^2\), the expression \(({\bf x},{\bf y})=x_1y_1+x_1y_2+x_2y_2\) is not an inner product: it is not symmetric. Eg \({\bf x}=(1,1)^T\) and \({\bf y}=(1,0)^T\) gives \(({\bf x},{\bf y})=1\) but \(({\bf y},{\bf x})=2\).

On \(V={\mathbb R}^2\), the expression \(({\bf x},{\bf y})=x_1y_1+x_1y_2+x_2y_1+x_2y_2\) is not an inner product: symmetry and bilinearity hold, but positivity does not. To see this, note that \(({\bf x},{\bf x})=(x_1+x_2)^2\), so for example \({\bf x}=(1,-1)\) is a non-zero vector with \(({\bf x},{\bf x})=0\).

On \(V={\mathbb R}^2\), the expression \(({\bf x},{\bf y})=x_1y_1+x_1y_2+x_2y_1+2x_2y_2\) is an inner product.

On \(V={\mathbb R}^3\), consider the expression \(({\bf x},{\bf y})=2x_1y_1+x_2y_2-2x_2y_3-2x_3y_2+kx_3y_3\), where \(k\in{\mathbb{R}}\) is fixed. This satisfies symmetry and bilinearity, so the question is whether positivity holds. To investigate this, observe that \(({\bf x},{\bf x})=2x_1^2+(x_2-2x_3)^2+(k-4)x_3^2\), so it is an inner product if and only if \(k>4\). (Note that the case \(k=4\) does not define an inner product.)

\(V=C[a,b]\), the vector space of continuous functions \(f:[a,b]\to{\mathbb R}\). (We assume \(a<b\).) Recall that \(V\) is infinite-dimensional, and that the zero vector is the function \(f\) which is identically zero. Define \[(f,g)=\int_a^bf(t)\,g(t)\,dt.\] (This scalar product is precisely the scalar product inducing the so called \(L^2\) norm over \(C[a,b]\).) Note that this is symmetric and bilinear. Also \[(f,f)=\int_a^bf(t)^2\,dt\geq0\] and if \(f(t)\) is not identically zero on \([a,b]\) then \((f,f)>0\). For in this case there exists \(t_0\in[a,b]\) such that \(f\left(t_0\right)=c\not=0\) and hence, using the continuity of \(f\), there is a small neighbourhood \((t_0-\delta,t_0+\delta)\), with \(\delta >0\), around \(t_0\) where \(f(t)^2\geq\frac{c^2}{4}\), so integrating gives \((f,f)=\int_a^bf(t)^2\,dt>0\). Conclusion: this is an inner product.

(Weighted version of the previous example.) Let \(k\colon [a,b]\to{\mathbb R}\) be such that \(k(t)>0\) for all \(t\in(a,b)\), with \(k\) a continuous function also called kernel, and define \((f,g)=\int_a^bk(t)\,f(t)\,g(t)\,dt\). More on this later.

(At this point you might want to go back to the Michaelmas lecture notes and refresh your memory about the vector space of polynomials with real coefficients.) Let \({\mathbb R}[x]_n\) denote the space of polynomials in \(x\), of degree at most \(n\), with real coefficients, i.e. \({\mathbb R}[x]_n = \{a_0+...+a_n x^n\,\mbox{with}\,a_i\in\mathbb{R}\}\). This is a vector space of dimension \(n+1\). For any interval \([a,b]\), it is a subspace of the infinite-dimensional space \(C[a,b]\) above. The form \((f,g)=\int_a^bf(t)\,g(t)\,dt\) is one choice of inner product. A natural basis is \(\{1,x,\ldots,x^{n-1},x^n\}\); so if \[p(x)=p_nx^n+\ldots+p_0\] is a polynomial, then its components with respect to this basis are \({\bf p}=(p_0,\ldots,p_n)\). The expression for \(({\bf p},{\bf q})\) depends on \(a\), \(b\) and \(n\). For \(a=0\), \(b=1\) and \(n=1\) we get \[({\bf p},{\bf q})=p_0 q_0 + \frac{1}{2}p_1 q_0 + \frac{1}{2}p_0 q_1 + \frac{1}{3}p_1 q_1.\]

In these notes \(\overline{z}=\mbox{Re}(z)-{\rm i}\,\mbox{Im}(z)\) denotes the complex conjugate of the complex number \(z=\mbox{Re}(z)+{\rm i}\,\mbox{Im}(z)\).

Note that \(\langle{\bf v},{\bf v}\rangle\) is always real, by hermiticity.

The first two properties constitute linearity in the first factor. Note that the inner product is not quite linear in the second factor, since we see that \(\langle{\bf u},\lambda{\bf v}\rangle =\overline{\lambda}\langle{\bf u},{\bf v}\rangle\), this property is sometimes called sesquilinearity.

We are using \((\ ,\ )\) for real inner products, and \(\langle\ ,\ \rangle\) for hermitian inner products, but this notation is not used by all authors.

Simplest case: \(V={\mathbb C}\). The standard inner product on \({\mathbb C}\) is \(\langle z,w\rangle=z\overline{w}\). Note that \(\langle z,z\rangle=|z|^2\).

The standard hermitian inner product on \({\mathbb C}^n\) is given by \(\langle{\bf z},{\bf w}\rangle=z_1\overline w_1+\dots+z_n\overline w_n\). Note that \(\langle{\bf z},{\bf z}\rangle=|z_1|^2+\ldots+|z_n|^2\).

\(V={\mathbb C}^2\) and \(\langle{\bf z},{\bf w}\rangle =3z_1\overline w_1+2z_2\overline w_2\).

\(V={\mathbb C}^2\) and \(\langle{\bf z},{\bf w}\rangle =3z_1\overline w_1+2z_2\overline w_2+{\rm i}z_1\overline w_2- {\rm i}z_2\overline w_1\). Note that hermiticity is satisfied, and the linearity properties are satisfied since the right hand side is linear in \(z_1,z_2\). For positivity, we have \[\begin{aligned} \langle{\bf z},{\bf z}\rangle &= 3z_1\overline z_1+2z_2\overline z_2 +{\rm i}z_1\overline z_2-{\rm i}z_2\overline z_1\\ &= 2|z_1|^2+|z_2|^2+|z_1-iz_2|^2\\ &\geq0,\end{aligned}\] with equality if and only if \(z_1=z_2=0\). So positivity is satisfied as well.

\(V={\mathbb C}^2\) and \(\langle{\bf z},{\bf w}\rangle =z_1\overline w_1+{\rm i}z_1\overline w_2-{\rm i}z_2\overline w_1+z_2\overline w_2\) satisfies linearity and hermiticity, but positivity fails, since \(\langle{\bf z},{\bf z}\rangle=|z_1-{\rm i}z_2|^2\) which is zero for \({\bf z}=(1,-{\rm i})\).

\(V={\mathbb C}^2\) and \(\langle{\bf z},{\bf w}\rangle =z_1\overline w_1+{\rm i}z_1\overline w_2+{\rm i}z_2\overline w_1+z_2\overline w_2\) is not hermitian.

Let \(V\) be the set of continuous complex-valued functions \(f:[a,b]\to{\mathbb C}\), with \(b>a\) and \[\langle f,g\rangle=\int_a^bf(t)\,\overline{g(t)}\,dt\] As an exercise, check that this defines an inner-product space.

Let \({\mathbb C}[x]_n\) denote the space of polynomials in \(x\), of degree at most \(n\), with complex coefficients. This is a complex vector space of complex dimension \(n+1\). For any interval \([a,b]\), it is a subspace of the infinite-dimensional space \(V\) above. A natural basis is \(\{1,x,\ldots,x^{n-1},x^n\}\); so if \[p(x)=p_nx^n+\ldots+p_0\] is a polynomial, then its components with respect to this basis are \({\bf p}=(p_0,\ldots,p_n)^T\). As for the real case \(\mathbb{R}[x]_n\), we could use \(\int_a^b\) as an inner product. For \(a=0\), \(b=1\) and \(n=1\) we get \[\langle{\bf p},{\bf q}\rangle=p_0 \overline{q_0} + \frac{1}{2}p_1 \overline{q_0} + \frac{1}{2}p_0 \overline{q_1} + \frac{1}{3}p_1 \overline{q_1},\] that can also be rewritten as \[\langle{\bf p},{\bf q}\rangle= (\overline{q_0},\overline{q_1}) \left( \begin{matrix} 1 && 1/2\\ 1/2 &&1/3 \end{matrix} \right) \left(\begin{matrix} p_0\\p_1 \end{matrix}\right)\,.\]

Note that from the absolute homogeneity property we have \(|| \bf{0} || =0\) and \(|| {\bf v}||=||-{\bf v}||\), so from the triangle inequality it follows that \[|| {\bf v}|| \geq 0\qquad\forall \,{\bf v}\in V \qquad\mbox{(non-negativity)}\,.\]

The triangle inequality takes its name from the well known fact that in a triangle the sum of the lengths of any two sides must be greater than or equal to the length of the remaining side.

Note that \(U^{\bot}\) is a vector subspace of \(V\).

The last equation is simply telling us that if we project first a vector \({\bf v}\) onto \(U\), and then take the component of this projection orthogonal to \(U\), or if we take the component of a vector \({\bf v}\) orthogonal to \(U\) and then project it onto \(U\), we always find the zero vector.

From the idempotency condition is really easy to see the eigenvalues of \(P\). Let \({\bf v}\) be an eigenvector of \(P\), with eigenvalue \(\lambda\), i.e. \(P {\bf v}= \lambda {\bf v}\), then since \(P^2 = P\) we get \[\lambda {\bf v}= P {\bf v}= P^2 {\bf v}= \lambda^2 {\bf v}\,,\] so the only possible eigenvalues are \(\lambda = 0\) and \(\lambda =1\) since \({\bf v}\neq {\bf 0}\).

In some contexts, \({\bf u_0}\) is known as a least-squares approximation to \({\bf v_0}\).

Consider \(V=\mathbb{R}^4\) equipped the standard inner product (and the norm induced by it), find the point in \[U={\rm span}\left\{{\bf v}_1=\left( \begin{matrix}0 \\ 2 \\ -1 \\ 2 \end{matrix}\right),\ {\bf v}_2=\left(\begin{matrix} 2 \\ 3 \\ 1 \\ 2 \end{matrix}\right)\right\}\] nearest to \[{\bf v}_0=\left(\begin{matrix} 1 \\ 1 \\ 1 \\ 1 \end{matrix}\right)\,.\]

Solution. We first need an orthonormal basis for \(U\). Now \(\Vert{\bf v}_1\Vert^2=9\), so the first unit vector in the Gram-Schmidt process is \[{\bf u}_1 =\frac{1}{3}\left(\begin{matrix} 0 \\ 2 \\ -1 \\ 2 \end{matrix}\right).\] Then \[\begin{aligned} {\bf \tilde v}_2 & = {\bf v}_2-\left({\bf v}_2,{\bf u}_1\right){\bf u_1} = \left(\begin{matrix} 2 \\ 3 \\ 1 \\ 2 \end{matrix}\right) -(6-1+4)\frac{1}{9}\left(\begin{matrix} 0 \\ 2 \\ -1 \\ 2 \end{matrix}\right) =\left( \begin{matrix} 2 \\ 1 \\ 2 \\ 0 \end{matrix}\right).\end{aligned}\] Then \(\Vert {\bf \tilde v}_2 \Vert^2=9\), so define \[{\bf u}_2=\frac{1}{3}\left(\begin{matrix} 2 \\ 1 \\ 2 \\ 0 \end{matrix}\right).\] Then \(\{{\bf u}_1,\,{\bf u}_2\}\) is an orthonormal basis for \(U\). The orthogonal projection of \({\bf v}_0\) onto \(U\) is \[\begin{aligned} {\bf u}_0 & = \left({\bf v}_0,{\bf u}_1\right){\bf u}_1 +\left({\bf v}_0,{\bf u}_2\right){\bf u}_2 ={3\over9}\left(\begin{matrix} 0 \\ 2 \\ -1 \\ 2 \end{matrix}\right) +{5\over9}\left(\begin{matrix} 2 \\ 1 \\ 2 \\ 0 \end{matrix}\right) =\frac{1}{9}\left(\begin{matrix} 10 \\ 11 \\ 7 \\ 6 \end{matrix}\right).\end{aligned}\] Using Pythagoras’ theorem gives \[\begin{aligned} \Vert {\bf v}_0-{\bf u}_0\Vert^2 & = \Vert {\bf v}_0\Vert ^2 -\Vert {\bf u}_0\Vert^2 \\ & = ({\bf v}_0,{\bf v}_0)- ({\bf v}_0,{\bf u}_1)^2-({\bf v}_0,{\bf u}_2)^2 \\ & = 4-1-25/9 \ = \ 2/9.\end{aligned}\] Note that \[{\bf v}_0-{\bf u}_0 =\frac{1}{9}\left(\begin{matrix} -1 \\ -2 \\ 2 \\ 3 \end{matrix}\right),\] and \(\Vert {\bf v}_0-{\bf u}_0\Vert^2=(1+4+4+9)/81=2/9\). This agrees!

Let \(V=C[-1,1]\) with the inner product \[(f,g)=\int_{-1}^1 f(t)g(t)\, dt.\] Find the linear polynomial \(f\) closest to \(g(t)=t^2+t\).

Solution. The space of linear polynomials is \(U={\rm span}(1,t)\). From example [ex:orthonormal-polynomial-basis], an orthonormal basis for \(U\) is \[\left\{ f_1=\frac{1}{ \sqrt{2}},\ f_2={\sqrt{3}\over\sqrt{2}}\,t\right\}.\] We have \[\begin{aligned} (g,f_1) & = \int_{-1}^1 \frac{1}{\sqrt{2}}(t^2+t)\, dt = \frac{1}{\sqrt{2}}\left[{t^3\over 3}+{t^2\over 2}\right]_{-1}^1 = \frac{\sqrt{2}}{3}, \\ (g,f_2) & = \int_{-1}^1\frac{\sqrt{3}}{\sqrt{2}}(t^3+t^2)\, dt = \frac{\sqrt{3}}{\sqrt{2}}\left[{t^4\over 4}+{t^3\over 3}\right]_{-1}^1 = \frac{\sqrt{2}}{\sqrt{3}}.\end{aligned}\] The orthogonal projection of \(g\) onto \(U\) is \[f(t)=(g,f_1)f_1+(g,f_2)f_2 ={\sqrt{2}\over 3}\,\frac{1}{ \sqrt{2}} +{\sqrt{2}\over \sqrt{3}}\,{\sqrt{3}\over\sqrt{2}}\,t =t+\frac{1}{ 3}.\] So this is the “best” (least-squares) straight-line fit to the parabola.

We can check this. Suppose that \(f=at+b\) then we want to find \(a\) and \(b\) that minimise \(\Vert g-f\Vert=\Vert t^2+t-at-b\Vert\). Now \[\begin{aligned} \Vert t^2+t-at-b\Vert^2 = & \int_{-1}^1dt\,\left( t^4+2t^3+t^2-2at^3-2at^2-2bt^2-2bt+\right.\\ &\qquad\,\, \left.+a^2t^2+2abt+b^2\right) \\ & = \left[\frac{t^5}{5}+\frac{t^4}{2}+\frac{t^3}{3} -\frac{at^4}{2}-\frac{2(a+b)t^3}{3}-bt^2 +\frac{a^2t^3}{3}+abt^2+b^2t\right]_{-1}^1 \\ & = \frac{2}{5}+\frac{2}{3}-\frac{4a}{3}-\frac{4b}{3}+\frac{2a^2}{3}+2b^2 \\ & = \frac{8}{45}+\frac{2}{3}(a-1)^2+2\left(b-\frac{1}{3}\right)^2,\end{aligned}\] where we completed the square in the last line. This is minimised when \(a=1\) and \(b=1/3\). That is \(f(t)=t+1/3\) as above.

Note that since \(\det(M) =\det(M^t)\), orthogonal matrices must have \(\mbox{det} M = \pm 1\).

Note that \(\det(U^*) = \overline{\det(U)}\), so a unitary matrix has \(\vert \det(U)\vert^2 =1\). In particular notice that \(U(1) = \{z\in\mathbb{C}\,\mbox{ such that }\, z\,z^* =z^*\,z= z\overline{z}=\vert z \vert ^2 =1\}\), so the determinant of every unitary matrix \(U\) is an element of \(U(1)\). A complex number with unit modulus, i.e. an element of \(U(1)\), is simply a point on the unit circle in the complex plane, so \(U(1) = \{ e^{i\phi}\,\mbox{with}\,\phi\in[0,2\pi]\}\), and the determinant of every unitary matrix takes the form \(\det(U)= e^{i \varphi}\) for some \(\varphi \in [0,2\pi]\).

\[\frac{1}{\sqrt{2}}\left(\begin{matrix}1 & 2 \\ 2 & 3\end{matrix}\right) \quad\mbox{is symmetric but not orthogonal.}\]

\[\frac{1}{\sqrt{2}}\left(\begin{matrix}1 & -1 \\ 1 & 1\end{matrix}\right) \quad\mbox{is orthogonal but not symmetric.}\]

\[\frac{1}{\sqrt{2}}\left(\begin{matrix}3 & 1 \\ 1 & 1\end{matrix}\right) \quad\mbox{is symmetric with $\det(M)=1$ but not orthogonal.}\]

\[\frac{1}{\sqrt{2}}\left(\begin{matrix}1 & 1 \\ 1 & -1\end{matrix}\right) \quad\mbox{is both symmetric and orthogonal.}\]

\[\frac{1}{\sqrt{2}}\left(\begin{matrix}1 & {\rm i}\\ -{\rm i}& 2\end{matrix} \right) \quad\mbox{is hermitian but not unitary.}\]

\[\frac{1}{\sqrt{2}}\left(\begin{matrix}1 & -{\rm i}\\ -{\rm i}& 1\end{matrix} \right) \quad\mbox{is unitary but not hermitian.}\]

Note that if \(A\) is symmetric real, then the eigenvectors can be taken to be real as well, because they satisfy \((A-\lambda I){\bf v}=0\) with \(A-\lambda I\in M_{n\times n}({\mathbb R})\), which has nonzero solutions over \({\mathbb R}\) since \(\det(A-\lambda I)=0\) (recall §3.6 of the Michaelmas lecture notes).

Proposition [prop:orthogonality-of-eigenvectors] implies that if the eigenvalues of \(A\) are all different, then we have \(n\) orthogonal (and linearly independent, by proposition [prop:diagonalizability-different-eigenvalues]) eigenvectors, so we can diagonalize by an orthogonal \(P\), after rescaling the eigenvectors so they have unit norm (recall proposition [prop:orthonormal-change-of-basis]). This fact remains true even if two eigenvalues approach each other: the eigenvectors remain orthogonal, and one can still diagonalize via a unitary (or orthogonal, in the real case) transformation even in the limit when eigenvalues coincide, as we now show.

\[A=\left(\begin{matrix} 2& -2\\ -2& 5\end{matrix}\right).\] The eigenvalues are \(\lambda=6,1\), and we get \[P=\frac{1}{\sqrt{5}}\left(\begin{matrix} 1& 2\\ -2& 1\end{matrix}\right).\]

\[A=\left(\begin{matrix} 2& -2& 0\\ -2& 1& -2\\ 0& -2& 0\end{matrix}\right)\] Characteristic polynomial: \[\begin{aligned} \det\left(\begin{matrix} t-2& 2& 0\\ 2& t-1& 2\\ 0& 2& t\end{matrix}\right) & = (t-2)[(t-1)t-4]-2\times2t\\ & = (t-2)[t^2-t-4]-4t\\ & = t^{3}-3\,t^{2}-6\,t+8\\ & = \left (t-1\right )\left (t+2\right )\left (t-4\right ).\\ \lambda & = 4,1,-2.\end{aligned}\] Eigenvectors:

• \(\lambda=4\) \[(4I-A){\bf x} = \left(\begin{matrix} 2& 2& 0\\2& 3& 2\\ 0& 2& 4\end{matrix}\right) \left(\begin{matrix} x_1 \\ x_2 \\ x_3 \end{matrix}\right) = \left(\begin{matrix}2x_1&+2x_2& \\ 2x_1&+3x_2&+2x_3\\ &2x_2&+4x_3\end{matrix}\right) = \left(\begin{matrix} 0 \\ 0 \\ 0 \end{matrix}\right).\] Unit eigenvector \[\frac{1}{3}\left(\begin{matrix} 2 \\ -2 \\ 1\end{matrix}\right).\]

• \(\lambda=1\) \[(I-A){\bf x} = \left(\begin{matrix} -1& 2& 0\\ 2& 0& 2\\ 0& 2& 1\end{matrix}\right) \left(\begin{matrix} x_1 \\ x_2 \\ x_3 \end{matrix}\right) = \left(\begin{matrix} -x_1& +2x_2&\\ 2x_1&& +2x_3\\ & 2x_2& +x_3\end{matrix}\right) = \left(\begin{matrix} 0 \\ 0 \\ 0 \end{matrix}\right).\] Unit eigenvector \[\frac{1}{3}\left(\begin{matrix} 2 \\ 1 \\ -2\end{matrix}\right).\]

• \(\lambda=-2\) \[(-2I-A){\bf x} = \left(\begin{matrix} -4& 2& 0\\ 2& -3& 2\\ 0& 2& -2\end{matrix}\right) \left(\begin{matrix} x_1 \\ x_2 \\ x_3 \end{matrix}\right) =\left(\begin{matrix} -4x_1& +2x_2&\\ 2x_1& -3x_2& +2x_3\\& 2x_2& -2x_3\end{matrix}\right) = \left(\begin{matrix} 0 \\ 0 \\ 0 \end{matrix}\right).\] Unit eigenvector \[\frac{1}{3}\left(\begin{matrix} 1 \\ 2 \\ 2 \end{matrix}\right).\]

Thus \[P=\frac{1}{3}\left(\begin{matrix} 2& 2& 1\\ -2& 1& 2\\ 1& -2& 2\end{matrix}\right)\qquad P^tAP=\left(\begin{matrix} 4& 0& 0\\ 0& 1& 0\\ 0& 0& -2\end{matrix}\right)\] : All the eigenvalues in the example are distinct, so the corresponding eigenvectors are automatically orthogonal to each other. If the eigenvalues are not distinct, then for repeated eigenvalues we must choose mutually orthogonal eigenvectors.

\[A = \left(\begin{matrix}4 & 1 -i \\ 1 + i & 5 \end{matrix}\right).\] Then \(A\) is hermitian, and the characteristic polynomial of \(A\) is given by \[\begin{aligned} \det (\lambda I - A) & = \det \left(\begin{matrix}\lambda - 4 & -1 +i \\ -1 - i & \lambda - 5 \end{matrix}\right) \\ & = \lambda^2 - 9 \lambda + 18 \\ & = (\lambda - 3)(\lambda - 6).\end{aligned}\] Thus the eigenvalues are \(\lambda = 3, 6\).

Corresponding unit eigenvectors:

\(\lambda = 3\): \[\frac{1}{\sqrt 3}\left(\begin{matrix}-1+i \\ 1 \end{matrix}\right).\] \(\lambda = 6\): \[\frac{1}{{\sqrt 6}}\left(\begin{matrix} 1-i \\ 2 \end{matrix}\right).\] (Note that these are mutually orthogonal.) Thus \[P = \left(\begin{matrix} -\frac{{1-i}}{{\sqrt 3}} & \frac{{1-i}}{{\sqrt 6}} \\ \frac{1}{{\sqrt 3}} & \frac{2}{{\sqrt 6}} \end{matrix}\right)\] is unitary and \[P^*AP =\left(\begin{matrix} 3&0 \\ 0&6 \end{matrix}\right).\]

(Diagonalization of real inner products)

Every real inner product on \({\mathbb R}^n\) may be written as \(({\bf u},{\bf v})={\bf y}^t A {\bf x}\), where \(A\) is a symmetric \(n\times n\) matrix and \({\bf x},\,{\bf y}\) are the coordinates of the two vectors \({\bf u},{\bf v}\) in the chosen basis.

If we change basis, the coordinates representing the two vectors \({\bf u},{\bf v}\) will change to \({\bf x}=M{\bf z},\,{\bf y}=M{\bf w}\) for some invertible matrix \(M\), where \({\bf z}\) and \({\bf w}\) are the coordinates of the vectors \({\bf u},{\bf v}\) in the new basis.

In the new basis the inner product will take the form \(({\bf u},{\bf v})={\bf y}^t A {\bf x} = {\bf w}^t M^t A M{\bf z} = {\bf w}^t B {\bf z}\), where the symmetric matrix \(B=M^t A M\) represents the same inner product but in a different basis.

As we have mentioned before, every symmetric matrix \(A\) can be orthogonally diagonalized, i.e. there exists an orthogonal matrix \(P\) such that \(PAP^t=D\), for \(D\) diagonal, then we have \[({\bf u},{\bf v})={\bf y}^t P^t D P {\bf x}=(P{\bf y})^t D (P{\bf x})={\bf {w}}^t D {\bf { z}}.\] So \({\bf x}\mapsto {\bf z}=P{\bf x},\,{\bf y}\mapsto {\bf w}=P{\bf y}\) is a change of basis which diagonalizes the inner product. In particular, \[({\bf v},{\bf v})=(P{\bf x})^t D (P{\bf x})= \lambda_1(z_1)^2+\ldots+\lambda_n(z_n)^2\] is positive if and only if the \(\lambda_i\) are all positive, in other words if and only if the matrix \(A\) is positive-definite.

(Diagonalization of hermitian inner products)

Similarly, every complex inner product on \({\mathbb C}^n\) may be written as \(\langle{\bf u},{\bf v}\rangle={\bf y}^* A {\bf x}\), where \(A\) is an hermitian \(n\times n\) matrix and \({\bf x},\,{\bf y}\) are the coordinates of the two vectors \({\bf u},{\bf v}\) in the chosen basis.

If we change basis, the coordinates representing the two vectors \({\bf u},{\bf v}\) will change to \({\bf x}=M{\bf z},\,{\bf y}=M{\bf w}\) for some invertible matrix \(M\), where \({\bf z}\) and \({\bf w}\) are the coordinates of the vectors \({\bf u},{\bf v}\) in the new basis.

In the new basis the inner product will take the form \(({\bf u},{\bf v})={\bf y}^* A {\bf x} = {\bf w}^* M^* A M{\bf z} = {\bf w}^* B {\bf z}\), where the hermitian matrix \(B=M^* A M\) represents the same inner product but in a different basis.

We can use the fact that every hermitian matrix can be unitarily diagonalized to write \(PAP^\ast=D\), with \(P\) unitary and \(D\) diagonal, so that we have \[\langle {\bf u},{\bf v}\rangle={\bf y}^\ast P^* D P {\bf x}=(P{\bf y})^\ast D (P{\bf x}).\] So \({\bf x}\mapsto {\bf z}=P{\bf x},\,{\bf y}\mapsto {\bf w}=P{\bf y}\) is a change of basis which diagonalizes the inner product. In particular, \[\langle{\bf v},{\bf v}\rangle=(P{\bf x})^* D (P{\bf x})= \lambda_1\vert z_1\vert^2+\ldots+\lambda_n\vert z_n\vert^2\] is positive if and only if the \(\lambda_i\) are all positive, in other words if and only if the matrix \(A\) is positive-definite.

Another famous example is that of Fourier series: in this case, we have orthonormal functions \[1/\sqrt{2},\, \cos(2\pi t),\, \sin(2\pi t),\, \ldots,\, \cos(2\pi nt),\, \sin(2\pi nt),\,\ldots,\] with the inner product \((f,g)=2 \int_{0}^1f(t)g(t)\,dt\). Since these are not polynomials, they do not quite fall into the framework being discussed here, but they are closely related.

In each case, the corresponding differential equation for \(f\) \[\mathcal{L} f =\lambda f\] says that \(f\) is an eigenfunction of the operator \({\cal L}\) with eigenvalue \(\lambda\). For example, the Legendre equation is \({\cal L}_Lf=-k(k+1)f\).

Note that the extra condition about degrees is satisfied for the five operators listed above.

So in the above five special cases, the corresponding (Legendre, Chebyshev etc) polynomials are eigenfunctions of the corresponding (Legendre, Chebyshev etc) operator.

Let \(V={\mathbb{R}}[x]_3\). Write down the matrix \(M\) representing the operator \({\cal L}_L\) acting on \(V\), using the basis \(\{1,x,x^2,x^3\}\) of \(V\). Use this to construct the Legendre polynomials \(\{f_0,f_1,f_2,f_3\}\).

Solution. The operator \({\cal L}_L\) maps \(1\) to \(0\), \(x\) to \(-2x\), \(x^2\) to \(2-6x^2\) and \(x^3\) to \(-12x^3+6x\); so its matrix is \[M=\left[\begin{array}{cccc}0 & 0 & 2 & 0 \\ 0 & -2 & 0 & 6 \\ 0 & 0 & -6 & 0 \\ 0 & 0 & 0 & -12 \end{array}\right].\]

\(M\) had to turn out to be upper-triangular, because of the “extra condition” referred to in remark [remark:extra-condition] regarding the degrees of \({\cal L}_L P\) and \(P\), i.e. \(\mbox{deg}\,{\cal L}_L P\leq \mbox{deg} \,P\) . So to get the eigenvalues is easy. The Legendre case has \({\cal L}x^n=-n(n+1)x^n+\text{(lower order terms)}\), so \(\lambda=-n(n+1)\) for \(n=0,1,2,3,\ldots\).

The eigenvalues here are \(\lambda=0,-2,-6,-12\).

For \(\lambda=0\), the eigenvector is \({\bf v}_0=[1\,\, 0\,\, 0\,\,0]^t\), and the corresponding eigenfunction is \(f_0=1\).

For \(\lambda=-2\), the eigenvector is \({\bf v}_1=[0\,\, 1\,\, 0\,\,0]^t\), and the corresponding eigenfunction is \(f_1=x\).

For \(\lambda=-6\), the eigenvector is \({\bf v}_2=[-1\,\, 0\,\, 3\,\,0]^t\), and the corresponding eigenfunction is \(f_2=3x^2-1\).

For \(\lambda=-12\), the eigenvector is \({\bf v}_3=[0\,\, -3\,\,0 \,\,5]^t\), and the corresponding eigenfunction is \(f_3=5x^3-3x\).

The corresponding normalized functions are the first four normalized Legendre polynomials.

If we rewrite this eigenfunction \(f\) using some basis, i.e. the basis of polynomials \(\{ 1,x,...,x^n,...\}\), the vector containing the coordinates of \(f\) in the basis used is an eigenvector of the associated matrix problem.

For example \(f_3=5x^2-3x\), computed above, is an eigenfunction of the Legendre operator with eigenvalue \(\lambda=-12\), while in the standard basis of \(\mathbb{R}[x]_3\), the vector \({\bf v}_3=(0,-3,0,5)\) represents the eigenfunction \(f_3\), and it is an eigenvector of the Legendre operator in matrix form.

Note that if \({\cal L}\) is hermitian, then so is \({\cal L}^n\) for positive integer \(n\) (the proof is left as an exercise).

Note that thanks to the properties of the complex inner product \(\langle\,\,,\,\rangle\) an anti-hermitian operator \({\cal L}_A\) can always be written as \({\cal L}_A = i\,{\cal L}\) with \({\cal L}\) hermitian \[\langle {\cal L}_A{\bf u},{\bf v}\rangle = i \langle {\cal L}{\bf u},{\bf v}\rangle =i \langle {\bf u},{\cal L}{\bf v}\rangle =-\langle {\bf u},i{\cal L}{\bf v}\rangle=-\langle {\bf u},{\cal L}_A {\bf v}\rangle\,.\]

On \({\mathbb{C}}^n\) with the standard basis and the standard inner product, a linear operator represented by the matrix \(M\) is hermitian if and only if the matrix is hermitian (\(M^*=M\)).

Let \(V\) be the space of differentiable complex-valued functions \(f(x)\) on \({\mathbb{R}}\), such that \(x^nf(x)\to0\) as \(x\to\pm\infty\) for every fixed value of \(n\). Define an hermitian inner product on \(V\) by \[\langle f,g\rangle = \int_{-\infty}^{\infty} f(x)\, \overline{g(x)}\,dx.\] Some examples of hermitian linear operators on \(V\) are:

• \(X:f(x)\mapsto xf(x)\), multiplication by \(x\);

• \(X^2:f(x)\mapsto x^2 f(x)\), multiplication by \(x^2\);

• \(P:f(x)\mapsto if'(x)\), differentiation plus multiplication by \(i\).

Any vector space \(V\) with the operation \(+\). In this case, the zero vector \({\bf0}\) is the identity, and the inverse of \({\bf v}\) is \(-{\bf v}\). This group structure is abelian. If \(V\) is a real 1-dimensional vector space, then this is the group \({\mathbb{R}}\) of real numbers under addition (ie. the operation is \(+\)).

The group \(\mathrm{GL}(n,{\mathbb{R}})\) of \(n\times n\) real invertible matrices, with \(P\bullet Q=PQ\) (matrix multiplication). Here the identity element is the identity \(n\times n\) matrix \({\bf I}\), and the inverse of a matrix in the group sense is just its inverse in the usual matrix sense. The fact that matrix multiplication is associative was shown in the Michaelmas term (proposition 2.3.1 of the Michaelmas term lecture notes). This group \(\mathrm{GL}(n,{\mathbb{R}})\) is not abelian, except for the case \(n=1\) when it is just the group of non-zero real numbers with multiplication as the operation.

The group \(\mathrm{GL}(n,{\mathbb{C}})\) of \(n\times n\) complex invertible matrices. The details are the same as for the previous example. Note that \(\mathrm{GL}(n,{\mathbb{R}})\) is a subgroup of \(GL(n,{\mathbb{C}})\).

The group \(\mathrm{SL}(n,{\mathbb{R}})\) of \(n\times n\) real matrices \(M\) having \(\det(M)=1\), is a subgroup of \(\mathrm{GL}(n,{\mathbb{R}})\):

1. closure follows from \(\det(PQ)=\det(P)\,\det(Q)=1\);

2. associativity is inherited from \(\mathrm{GL}(n,{\mathbb{R}})\);

3. \({\bf I}\) is in the set, since \(\det({\bf I})=1\);

4. if \(\det(M)=1\), then \(\det(M^{-1})=1\).

The group \(O(n)\) of \(n\times n\) real orthogonal matrices, is a subgroup of \(\mathrm{GL}(n,{\mathbb{R}})\):

1. if \(A\) and \(B\) are orthogonal, then \((AB)(AB)^t=ABB^tA^t=AA^t={\bf I}\), so \(AB\) is orthogonal;

2. associativity is inherited from \(\mathrm{GL}(n,{\mathbb{R}})\);

3. \({\bf I}\) is orthogonal;

4. if \(A\) is orthogonal, then \(A^{-1}=A^t\) by definition, so \((A^{-1})(A^{-1})^t=A^tA={\bf I}\), so \(A^{-1}\) is orthogonal.

The group \(SO(n)\) of \(n\times n\) real orthogonal matrices \(M\) having \(\det(M)=1\). This is a subgroup both of \(O(n)\) and of \(\mathrm{SL}(n,{\mathbb{R}})\). The group \(SO(2)\) is particularly simple: if \(P\in SO(2)\) we can write \[P=\left(\begin{matrix} a & b \\ c& d\end{matrix}\right)\,,\] and \[P^t=\left(\begin{matrix} a & c \\ b& d\end{matrix}\right)\,,\] with \(a,b,c,d\in {\mathbb R}\). The orthogonality condition \(P^tP=P\,P^t=I\) plus the extra condition that \(\det(P) = 1\) is equivalent to the system of equations \[\left\lbrace \begin{matrix} a^2 + c^2=1 \,,\phantom{\qquad(\mbox{det}P=+1)}\\ a b + c d=0 \,,\phantom{\qquad(\mbox{det}P=+1)}\\ b^2 + d^2=1\,,\phantom{\qquad(\mbox{det}P=+1)}\\ ad-bc =1\,. \,\,\quad(\det(P)=+1) \end{matrix}\right.\] We can easily solve this system and the most generic \(P\in SO(2)\) takes the form \[P=\left(\begin{matrix} \cos\,\theta & -\sin\,\theta \\ \sin\,\theta& \cos\,\theta\end{matrix}\right)\,,\] where the rotation angle \(\theta \in [0,2\pi]\). We say that \(SO(2)\) is isomorphic to \(S^1 = \{(a,c)\in\mathbb{R}^2 \,\mbox{such that} \,a^2+c^2=1\}\).

The group \(\mathrm{SL}(n,{\mathbb{C}})\) of \(n\times n\) complex matrices \(M\) having \(\det(M)=1\); the group \(U(n)\) of \(n\times n\) complex unitary matrices; and the group \(SU(n)\) of \(n\times n\) complex unitary matrices \(M\) having \(\det(M)=1\).

The integers \({\mathbb{Z}}\) with operation \(+\) forms an abelian group. If \(n\) is an integer with \(n\geq2\), then we may define an equivalence relation on \({\mathbb{Z}}\) by \(p\sim q\) if and only if \(n\) divides \(p-q\); this is also written \(p\equiv q\) (mod \(n\)). The set \({\mathbb{Z}}_n\) of equivalence classes forms a finite abelian group of order \(n\), with addition as the group operation (note that \(+\) is well-defined on equivalence classes). This group \({\mathbb{Z}}_n\) is also called the cyclic group of order \(n\). (Alternative notations for this group are \({\mathbb{Z}}/n\) and \({\mathbb{Z}}/n{\mathbb{Z}}\).) For example, the group \({\mathbb{Z}}_4\) has elements \(\{\overline{0}, \overline{1},\overline{2},\overline{3}\}\), and the group operation of addition modulo 4 is expressed in the group table

+	\(\overline{0}\)	\(\overline{1}\)	\(\overline{2}\)	\(\overline{3}\)
\(\overline{0}\)	\(\overline{0}\)	\(\overline{1}\)	\(\overline{2}\)	\(\overline{3}\)
\(\overline{1}\)	\(\overline{1}\)	\(\overline{2}\)	\(\overline{3}\)	\(\overline{0}\)
\(\overline{2}\)	\(\overline{2}\)	\(\overline{3}\)	\(\overline{0}\)	\(\overline{1}\)
\(\overline{3}\)	\(\overline{3}\)	\(\overline{0}\)	\(\overline{1}\)	\(\overline{2}\)

There are exactly two groups of order 4, namely \({\mathbb{Z}}_4\) as above, and the Klein group \(V\) which has the table

\(\bullet\)	\(e\)	\(a\)	\(b\)	\(c\)
\(e\)	\(e\)	\(a\)	\(b\)	\(c\)
\(a\)	\(a\)	\(e\)	\(c\)	\(b\)
\(b\)	\(b\)	\(c\)	\(e\)	\(a\)
\(c\)	\(c\)	\(b\)	\(a\)	\(e\)

The fact that this group is abelian is encoded in the fact that this table is symmetric.

Note that the group table of \({\mathbb{Z}}_4\) has a quite different structure from that of \(V\). One visualisation (or representation) of \(V\) is as the group of rotations by \(180^\circ\) about each of the \(x\)-, \(y\)- and \(z\)-axes in \({\mathbb{R}}^3\) (ie. the element \(a\) corresponds to rotation by \(\pi\) about the \(x\)-axis, etc). As an exercise: by using a marked cube such as a die, convince yourself that \(a\bullet b=c\).

Another representation of \(V\) is as the group of reflections across the \(x-\)axis, the \(y-\)axis, and a combined reflection across the \(x-\)axis and then the \(y-\)axis, in \(\mathbb{R}^2\). Take \[e=\left[\begin{array}{cc}1 & 0 \\ 0 & 1\end{array}\right],\quad a=\left[\begin{array}{cc}1 & 0 \\ 0 & -1\end{array}\right],\quad b=\left[\begin{array}{cc}-1 & 0 \\ 0 & 1\end{array}\right],\quad c=\left[\begin{array}{cc}- 1 & 0 \\ 0 & -1\end{array}\right],\] and see that these matrices satisfy the group table of the Klein group using as group operation the matrix multiplication.

In \({\mathbb{Z}}\), no element other than the identity has finite order. But in \({\mathbb{Z}}_n\), every element has finite order. Observe that the elements \(a\), \(b\), \(c\) of the Klein group \(V\) all have order \(2\); whereas in \({\mathbb{Z}}_4\), \(\overline{2}\) has order \(2\) and \(\overline{1},\overline{3}\) have order \(4\). In a matrix group like \(\mathrm{GL}(2,{\mathbb{C}})\), most elements have infinite order, but some have finite order: eg \(A={\rm{diag}}(1,-1)\) has order \(2\).

The direct product of two cyclic groups of order 2 is \(\mathbb{Z}_2\times \mathbb{Z}_2\). This group has \(4\) elements, i.e. \(\{(\overline{0},\overline{0}),(\overline{1},\overline{0}),(\overline{0},\overline{1}),(\overline{1},\overline{1})\}\). The element \((\overline{0},\overline{0})\) is the identity element in \(\mathbb{Z}_2\times \mathbb{Z}_2\) and the group table is given by

\(+\)	\((\overline{0},\overline{0})\)	\((\overline{1},\overline{0})\)	\((\overline{0},\overline{1})\)	\((\overline{1},\overline{1})\)
\((\overline{0},\overline{0})\)	\((\overline{0},\overline{0})\)	\((\overline{1},\overline{0})\)	\((\overline{0},\overline{1})\)	\((\overline{1},\overline{1})\)
\((\overline{1},\overline{0})\)	\((\overline{1},\overline{0})\)	\((\overline{0},\overline{0})\)	\((\overline{1},\overline{1})\)	\((0,1)\)
\((\overline{0},\overline{1})\)	\((\overline{0},\overline{1})\)	\((\overline{1},\overline{1})\)	\((\overline{0},\overline{0})\)	\((\overline{1},\overline{0})\)
\((\overline{1},\overline{1})\)	\((\overline{1},\overline{1})\)	\((\overline{0},\overline{1})\)	\((\overline{1},\overline{0})\)	\((\overline{0},\overline{0})\)

Comparing with example [ex:klein-group], we see that there is an isomorphism \(\{(\overline{0},\overline{0}), (\overline{1},\overline{0}), (\overline{0},\overline{1}), (\overline{1},\overline{1})\}\to \{e,a,b,c\}\), so \(\mathbb{Z}_2\times \mathbb{Z}_2\) is isomorphic to the Klein group.

Take the direct product of two cyclic groups \(\mathbb{Z}_4\times \mathbb{Z}_3\), and consider the element \((\overline 2, \overline 2)\). The order of \(\overline 2\) in \(\mathbb{Z}_4\) is 2 while the order of \(\overline 2\) in \(\mathbb{Z}_3\) is 3 so the order of \((\overline 2, \overline 2)\) in \(\mathbb{Z}_4\times \mathbb{Z}_3\) is \(6\). And indeed we have \[\begin{aligned} &(\overline 2, \overline 2)^1 =(\overline 2, \overline 2)\qquad (\overline 2, \overline 2)^2= (\overline 0, \overline 1)\qquad (\overline 2, \overline 2)^3 = (\overline 2, \overline 0)\\ & (\overline 2, \overline 2)^4 = (\overline 0, \overline 2)\qquad (\overline 2, \overline 2)^5 = (\overline 2, \overline 1)\qquad (\overline 2, \overline 2)^6 = (\overline 0, \overline 0). \end{aligned}\]

For \(n=1\) we have \(O(1)=\{1,-1\}={\mathbb{Z}}_2\). The group operation is multiplication, the element 1 is the identity, and the element \(-1\) is the reflection \(x\mapsto-x\).

This group \(O(1)\) is finite and abelian, but \(O(n)\) for \(n\geq2\) is neither finite nor abelian. For instance take the following two elements of \(O(2)\): \[A=\begin{pmatrix}1&0\\0& -1\end{pmatrix} \qquad ;\qquad B = \begin{pmatrix}0&-1\\1& 0\end{pmatrix}\, .\] A short computation shows that \(AB\neq BA\), so \(O(2)\) is not abelian. It is also not finite, since \(SO(2)\) is a subgroup, and \(SO(2)\) is not finite: recall from example [eq:SO(2)] that we have an element of \(SO(2)\) for each angle \(\theta\in[0,2\pi)\). Finally, note that we can build non-commuting elements in \(O(n)\) for any \(n>2\) by taking the block diagonal matrices \(C_n={\rm{diag}}(A,I_{n-2})\), \(D_n={\rm{diag}}(B,I_{n-2})\), where \(I_{n-2}\) is the \((n-2)\times (n-2)\) identity matrix.

Recall from remark [remark:orthogonal-determinant] that any orthogonal matrix \(M\) has \(\det(M)=\pm1\). Any element \(M\) of \(O(n)\) with \(\det(M)=-1\) gives an element \(P=MN\) with \(\det(P)=+1\) when composed with another element \(N\) of \(O(n)\) with \(\det(N)=-1\). An example of such an element is reflection along the first coordinate: \[R_1 = \begin{pmatrix} -1 \\ & 1 \\ && 1 \\ &&& \ddots \\ &&&& 1 \end{pmatrix}\] which clearly has \(\det(R_1)=-1\). So we can view elements of \(O(n)\) as elements with \(\det(M)=+1\) composed with reflections. This motivates the following definition, encoding the geometric intuition that the transformations preserving inner products are rotations and reflections.

\(SO(1)\) is trivial, \(SO(2)\) is abelian, and \(SO(n)\) for \(n\geq3\) is not abelian. That \(SO(2)\) is abelian follows from the explicit form we found in example [eq:SO(2)] (you can easily show that two matrices of that form always commute; intuitively it does not matter if you first rotate by and angle \(\alpha\) and then by \(\beta\), or in the opposite order). To show that \(SO(3)\) is not abelian we can use the block diagonal matrices \(X={\rm{diag}}(A,-1)\), \(Y={\rm{diag}}(B,1)\), where \(A\) and \(B\) are as in remark [remark:O(n)]. You can easily check that \(X,Y\in SO(3)\) and \(XY\neq YX\). You can now extend \(X\), \(Y\) to non-commuting matrices in \(SO(n)\) for any \(n>3\) as we did in remark [remark:O(n)], by constructing block diagonal matrices \({\rm{diag}}(X,I_{n-3})\), \({\rm{diag}}(Y,I_{n-3})\).

Solve the system of ODEs \[\begin{aligned} \dot{x} & = x+y, \\ \dot{y} & = -x+3y. \end{aligned}\] Solution. The system has the form \(\dot{\bf u}=A{\bf u}\), where \[A=\left(\begin{matrix} 1 & 1 \\ -1 & 3 \end{matrix}\right).\] The characteristic polynomial of \(A\) is \(p(t)=(t-2)^2\), so \(A\) has the double eigenvalue \(\lambda=2\). There is only one eigenvector, namely \({\bf w}=(1,1)\), so \(A\) cannot be diagonalized. To get \({\bf v}\) we solve \((A-2I){\bf v}={\bf w}\), and one solution is \({\bf v}=(1,2)\) — this is not the only solution, but that doesn’t matter. Thus \(M^{-1}AM=J\), where \[M=\left(\begin{matrix} 1 & 1 \\ 1 & 2 \end{matrix}\right), \quad J=\left(\begin{matrix} 2 & 1 \\ 0 & 2 \end{matrix}\right).\] If \({\bf s}=M^{-1}{\bf u}\), then the original system becomes \(\dot s_1=2s_1+s_2\), \(\dot s_2=2s_2\), which is easily solved to give \(s_2(t)=c_2\exp(2t)\), \(s_1(t)=(c_1+c_2t)\exp(2t)\). (Exercise for you: obtain this.) Finally, transform back to \({\bf u}=M{\bf s}\), giving \[x(t)=(c_1+c_2+c_2t)\exp(2t), \quad y(t)=(c_1+2c_2+c_2t)\exp(2t).\] (Exercise for you: check this by substitution.)

Explicitly, for \(n\leq 3\) we have: \[J_1^{(\lambda)} = \begin{pmatrix} \lambda \end{pmatrix} \qquad ; \qquad J_2^{(\lambda)} = \begin{pmatrix} \lambda & 1 \\ 0 & \lambda \end{pmatrix} \qquad ; \qquad J_3^{(\lambda)} = \begin{pmatrix} \lambda & 1 & 0 \\ 0 & \lambda & 1 \\ 0 & 0 & \lambda \end{pmatrix}\, .\]

Here are some properties of \(N\):

1. Since the \(J_{n_i}^{(\lambda_i)}\) are therefore \(N\) are upper triangular \(p_N(t)=(\lambda_1-t)^{n_1}\cdots (\lambda_k-t)^{n_k}\). So \(\lambda_i\) are the eigenvalues of \(N\).

2. Fix some eigenvalue \(\lambda\) of \(N\). Then the algebraic multiplicity of \(\lambda\) is the sum of the \(n_i\) where \(\lambda_i=\lambda\).

3. On the other hand, the geometric multiplicity of some eigenvalue \(\lambda\) is the number of Jordan blocks \(J_{n_i}^{(\lambda_i)}\) such that \(\lambda_i=\lambda\). To show this, notice (by solving \(J^{(\lambda_i)}_{n_i}{\bf v}=\lambda_i {\bf v}\)) that the geometric multiplicity associated to each Jordan block is precisely one.

4. The two statements above imply that \(N\) will be diagonalizable if and only if all \(n_i=1\), because only in this case do the geometric and algebraic multiplicities of all eigenvalues coincide. So a matrix \(N\) in Jordan normal form is diagonalizable if and only if it is diagonal.

Find the Jordan normal form of \[A=\left(\begin{matrix} 2 & 2 & -2 \\ 1 & -1 & 1 \\ 2 & 0 & 0 \end{matrix}\right).\]

Solution. We first calculate the characteristic polynomial: \[p_A(t)=\det(A-tI) =\det\left(\begin{matrix} 2-t & 2 & -2 \\ 1 & -1-t & 1 \\ 2 & 0 & -t\end{matrix}\right) =-t^3+t^2=(1-t)t^2.\] Thus the eigenvalues are \(\lambda=1\) and \(\lambda=0\) (twice).

• \(\lambda=1\) \[\left(\begin{matrix} 0 \\ 0 \\ 0\end{matrix}\right)=(A-I){\bf x} = \left(\begin{matrix} 1 & 2 & -2 \\ 1 & -2 & 1 \\ 2 & 0 & -1\end{matrix}\right) \left(\begin{matrix} x_1 \\ x_2 \\ x_3\end{matrix}\right).\] So \(x_3=2x_1\) and \(2x_2=-x_1+2x_3=3x_1\). An eigenvector is \[{\bf u}_1=\left(\begin{matrix} 2 \\ 3 \\ 4\end{matrix}\right).\]

• \(\lambda=0\) \[\left(\begin{matrix} 0 \\ 0 \\ 0\end{matrix}\right)=(A-0I){\bf x}= A{\bf x} = \left(\begin{matrix} 2 & 2 & -2 \\ 1 & -1 & 1 \\ 2 & 0 & 0\end{matrix}\right) \left(\begin{matrix} x_1 \\ x_2 \\ x_3\end{matrix}\right).\] So \(x_1=0\) and \(x_2=x_3\). An eigenvector is \[{\bf u}_2=\left(\begin{matrix} 0 \\ 1 \\ 1\end{matrix}\right).\] The \(0\)-eigenspace is spanned by \({\bf u}_2\). So to calculate the Jordan normal form, we must solve \(A{\bf x}={\bf u}_2\), which gives \[\left(\begin{matrix} 2 & 2 & -2 \\ 1 & -1 & 1 \\ 2 & 0 & 0\end{matrix}\right) \left(\begin{matrix} x_1 \\ x_2 \\ x_3\end{matrix}\right) = \left(\begin{matrix} 0 \\ 1 \\ 1\end{matrix}\right).\] Hence we can take \[{\bf x}={\bf u}_3=\left(\begin{matrix} 1/2 \\ -1/2 \\ 0\end{matrix}\right).\]

Let \(M\) be the matrix whose columns are \({\bf u}_1\), \({\bf u}_2\) and \({\bf u}_3\). Then \[M=\left(\begin{matrix} 2 & 0 & 1/2 \\ 3 & 1 & -1/2 \\ 4 & 1 & 0\end{matrix}\right),\qquad M^{-1}=\left(\begin{matrix} 1 & 1 & -1 \\ -4 & -4 & 5 \\ -2 & -4 & 4 \end{matrix}\right),\] and \[M^{-1}AM=\left(\begin{matrix} 1 & 0 & 0 \\ 0 & 0 & 1 \\ 0 & 0 & 0\end{matrix}\right).\] This is the Jordan normal form of \(A\). It has a \(1\times 1\) block associated with \(\lambda=1\), and a \(2\times 2\) block associated with \(\lambda=0\).

If \(\lambda\) is a triple eigenvalue, and there is only one eigenvector \({\bf w}\), then we just iterate the process. Solve \((A-\lambda I){\bf v}={\bf w}\) to get \({\bf v}\), then solve \((A-\lambda I){\bf u}={\bf v}\) to get \({\bf u}\); and take \(M\) to have the three columns \({\bf w}\), \({\bf v}\), \({\bf u}\).

Find the Jordan normal form of \[A=\left(\begin{matrix} 1 & 1 & 0 \\ 0 & 2 & 1 \\ 1 & -1 & 3\end{matrix}\right).\]

Solution. We first calculate the characteristic polynomial of \(A\): \[p_A(t)=\det(A-tI) =\det\left(\begin{matrix} 1-t & 1 & 0 \\ 0 & 2-t & 1 \\ 1 & -1 & 3-t\end{matrix}\right)=(2-t)^3.\] Therefore the only eigenvalue is \(\lambda=2\), of algebraic multiplicity 3. We first solve \[\left(\begin{matrix} 0 \\ 0 \\ 0\end{matrix}\right)=(A-2I){\bf x} =\left(\begin{matrix} -1 & 1 & 0 \\ 0 & 0 & 1 \\ 1 & -1 & 1\end{matrix}\right) \left(\begin{matrix} x_1 \\ x_2 \\ x_3\end{matrix}\right).\] The solutions satisfy \(x_1=x_2\), \(x_3=0\). So we can take \[{\bf u}_1=\left(\begin{matrix} 1 \\ 1 \\ 0\end{matrix}\right).\] Now we look for a solution of \((A-2I){\bf x}= {\bf u}_1\), which gives \[{\bf x}= {\bf u}_2=\left(\begin{matrix} 0 \\ 1 \\ 1\end{matrix}\right).\] Finally, we solve \((A-2I){\bf x}={\bf u}_2\), which gives the third root vector \[{\bf x}={\bf u}_3=\left(\begin{matrix} 0 \\ 0 \\ 1\end{matrix}\right).\] Now if \(M\) is the matrix whose columns are \({\bf u}_1\), \({\bf u}_2\) and \({\bf u}_3\), we have \[M=\left(\begin{matrix} 1 & 0 & 0 \\ 1 & 1 & 0 \\ 0 & 1 & 1\end{matrix}\right),\qquad M^{-1}=\left(\begin{matrix} 1 & 0 & 0 \\ -1 & 1 & 0 \\ 1 & -1 & 1\end{matrix}\right),\] and \[M^{-1}AM=\left(\begin{matrix} 2 & 1 & 0 \\ 0 & 2 & 1 \\ 0 & 0 & 2\end{matrix}\right).\] This is the Jordan normal form of \(A\). It has a single \(3\times 3\) Jordan block associated with \(\lambda=2\).

Note that these choices are not unique. We could have chosen \[{\bf u}_2=\left(\begin{matrix} 1 \\ 2 \\ 1\end{matrix}\right);\] and then we can choose \[{\bf u}_3=\left(\begin{matrix} -1 \\ 0 \\ 2\end{matrix}\right)\quad \hbox{ or }\quad \left(\begin{matrix} 0 \\ 1 \\ 2\end{matrix}\right).\]

Find the Jordan normal form of \[A=\left(\begin{matrix} -2 & -6 & 6 & 15 \\ 0 & 7 & 0 & -15 \\ -2 & -4 & 5 & 10 \\ 0 & 2 & 0 & -4 \end{matrix}\right),\] using the fact that \(p_A(t)=(t-2)^2(t-1)^2\).

Solution.

• \(\lambda =2\) \[{\bf 0}=(A-2I){\bf x}= \left(\begin{matrix} -4 & -6 & 6 & 15 \\ 0 & 5 & 0 & -15 \\ -2 & -4 & 3 & 10 \\ 0 & 2 & 0 & -6 \end{matrix}\right) \left(\begin{matrix} x_1 \\ x_2 \\ x_3 \\ x_4\end{matrix}\right)\] has solutions \[\begin{aligned} -4x_1-6x_2+6x_3+15x_4 &= 0, \\ x_2-3x_4 &= 0,\\ -2x_1-4x_2+3x_3+10x_4 &= 0. \end{aligned}\] Subtracting to the first two times the third one gives \(2x_2-5x_4=0\) which combined with the second equation gives \(x_2 = x_4=0\) and hence \(2x_1=3x_3\). Therefore \[\dim \ker \bigl((A-2I)\bigr)=1,\] and it is spanned by \[{\bf u}_1=\left(\begin{matrix} 3 \\ 0 \\ 2 \\ 0\end{matrix}\right)\] Next \[{\bf 0}=(A-2I)^2{\bf x}= \left(\begin{matrix} 4 & 0 & -6 & 0 \\ 0 & -5 & 0 & 15 \\ 2 & 0 & -3 & 0 \\ 0 & -2 & 0 & 6 \end{matrix}\right) \left(\begin{matrix} x_1 \\ x_2 \\ x_3 \\ x_4\end{matrix}\right)\] has solutions \[\begin{aligned} 2x_1-3x_3 &= 0,\\ x_2-3x_4 &= 0. \end{aligned}\] Therefore \[\dim \ker \bigl((A-2I)^2\bigr)=2,\] and it is spanned by \[{\bf u}_1=\left(\begin{matrix} 3 \\ 0 \\ 2 \\ 0\end{matrix}\right),\ {\bf u}_2=\left(\begin{matrix} 0 \\ 3 \\ 0 \\ 1\end{matrix}\right),\ \] In fact, \(A{\bf u}_2=2{\bf u}_2-{\bf u}_1\). The associated Jordan block is \[\left(\begin{matrix} 2 & 1 \\ 0 & 2 \end{matrix}\right).\]

• \(\lambda=1\) \[{\bf 0}=(A-I){\bf x}= \left(\begin{matrix} -3 & -6 & 6 & 15 \\ 0 & 6 & 0 & -15 \\ -2 & -4 & 4 & 10 \\ 0 & 2 & 0 & -5 \end{matrix}\right) \left(\begin{matrix} x_1 \\ x_2 \\ x_3 \\ x_4\end{matrix}\right)\] This has solutions \[\begin{aligned} -x_1-2x_2+2x_3+5x_4 &= 0, \\ 2x_2-5x_4 &=0. \end{aligned}\] Thus \[\dim \ker \bigl((A-I)\bigr)=2,\] and it is spanned by \[{\bf u}_3=\left(\begin{matrix} 2 \\ 0 \\ 2 \\ 0\end{matrix}\right),\ {\bf u}_4=\left(\begin{matrix} 0 \\ 5 \\ 0 \\ 2\end{matrix}\right).\]

Thus we obtain two Jordan blocks of the form \((1)\).

Hence the Jordan normal form of \(A\) is \[J=\left(\begin{matrix} 2 & 1 & 0 & 0 \\ 0 & 2 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1\end{matrix}\right).\] Indeed, if \(M\) is the matrix whose columns are \(-{\bf u}_1\), \({\bf u}_2\), \({\bf u}_3\), \({\bf u}_4\), then \(M^{-1}AM=J\).

Find the Jordan normal form of \[A=\left(\begin{matrix} 0 & 4 & 4 \\ -2 & 6 & 4 \\ 1 & -2 & 0\end{matrix}\right).\]

Solution. We first calculate the characteristic polynomial of \(A\): \[p_A(t)=\det(A-tI) =\det\left(\begin{matrix} -t & 4 & 4 \\ -2 & 6-t & 4 \\ 1 & -2 & -t \end{matrix}\right)=(2-t)^3.\] Next we solve \[\left(\begin{matrix} 0 \\ 0 \\ 0\end{matrix}\right)=(A-2I){\bf x} =\left(\begin{matrix} -2 & 4 & 4 \\ -2 & 4 & 4 \\ 1 & -2 & -2\end{matrix}\right) \left(\begin{matrix} x_1 \\ x_2 \\ x_3\end{matrix}\right).\] These solutions lie on the plane \(x_1-2x_2-2x_3=0\), which is 2-dimensional. We choose two independent vectors in the plane \[{\bf u}_1=\left(\begin{matrix} 2 \\ 1 \\ 0\end{matrix}\right) \qquad \text{and} \qquad {\bf u}_2\mathrel{\mathop:}\mathrel{\mkern-1.2mu}=\left(\begin{matrix} 2 \\ 2 \\ -1\end{matrix}\right)\, .\] To find a third vector, we solve \((A-2I){\bf u}_3={\bf u}_2\). This equation will have a solution since \(\dim \ker \bigl((A-2I)\bigr)=2\) and \(\dim \ker \bigl((A-2I)^2\bigr)=3.\)

We take \[{\bf u}_3=\left(\begin{matrix} -1 \\ 0 \\ 0\end{matrix}\right).\]

Define \[M=\left(\begin{matrix} 2 & 2 & -1 \\ 1 & 2 & 0 \\ 0 & -1 & 0 \end{matrix}\right), \qquad M^{-1}=\left(\begin{matrix} 0 & 1 & 2 \\ 0 & 0 & -1 \\ -1 & 2 & 2 \end{matrix}\right),\] and then \[M^{-1}AM=\left(\begin{matrix} 2 & 0 & 0 \\ 0 & 2 & 1 \\ 0 & 0 & 2 \end{matrix}\right).\]

Find the Jordan normal form of \[A=\left(\begin{matrix} 1 & 1 & 0 \\ 0 & 2 & 0 \\ 0 & 0 & 2\end{matrix}\right).\]

Solution. We first calculate the characteristic polynomial of \(A\): \[p_A(t)=\det(A-tI) =\det\left(\begin{matrix} 1-t & 1 & 0 \\ 0 & 2-t & 0 \\ 0 & 0 & 2-t \end{matrix}\right)=(1-t)(2-t)^2.\] So the eigenvalues are \(\lambda=1\) and \(\lambda=2\).

1. \(\lambda=1\) \[\left(\begin{matrix} 0 \\ 0 \\ 0\end{matrix}\right) = (A-I){\bf x}= \left(\begin{matrix} 0 & 1 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1\end{matrix}\right) \left(\begin{matrix} x_1 \\ x_2 \\ x_3\end{matrix}\right).\] The solutions are \(x_2=x_3=0\), so we take \[{\bf u}_1=\left(\begin{matrix} 1 \\ 0 \\ 0\end{matrix}\right).\]

2. \(\lambda=2\) \[\left(\begin{matrix} 0 \\ 0 \\ 0\end{matrix}\right) = (A-2I){\bf x}= \left(\begin{matrix} -1 & 1 & 0 \\ 0 & 0 & 0 \\ 0 & 0 & 0\end{matrix}\right) \left(\begin{matrix} x_1 \\ x_2 \\ x_3\end{matrix}\right).\] The solutions are \(x_1=x_2\). This is 2-dimensional, so we take two linearly independent eigenvectors \[{\bf u}_2=\left(\begin{matrix} 1 \\ 1 \\ 0\end{matrix}\right), \qquad {\bf u}_3=\left(\begin{matrix} 0 \\ 0 \\ 1\end{matrix}\right).\]

Define \(M\) to be the matrix whose columns are the \({\bf u}_j\): \[M=\left(\begin{matrix} 1 & 1 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{matrix}\right),\qquad P^{-1}=\left(\begin{matrix} 1 & -1 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{matrix}\right).\] Then \[M^{-1}AM=\left(\begin{matrix} 1 & 0 & 0 \\ 0 & 2 & 0 \\ 0 & 0 & 2 \end{matrix}\right).\]

If the matrix \(M\) has eigenvalue \(\lambda\), then \(A=M-\lambda{\bf I}\) has \(\det(A)=0\), and the solutions of \(A{\bf x}={\bf 0}\) are exactly the eigenvectors in the eigenspace \(V_{\lambda}\).

Note that \[A{\bf x}={\bf k}\Rightarrow A^tA{\bf x}=A^t{\bf k}\Rightarrow {\bf x}=(A^tA)^{-1}A^t{\bf k}=\psi(A){\bf k}\] which partially justifies the name “pseudoinverse” for \(\psi(A)\). Additionally, if \(m=n\), then \[\psi(A)=(A^tA)^{-1}A^t=A^{-1}(A^t)^{-1}A^t=A^{-1}\, .\]

Note that with these definitions the polynomial \(y_{{\bf a}}(x)\) would pass through the given data points if \({\bf y}=X{\bf a}\). In general it is not possible choose an \({\bf a}\) such that this holds, since the system is overdetermined, so we try to find the polynomial that ends up closest to the given data points.

Find the line which best fits the data points \((1,1)\), \((2,2.4)\), \((3,3.6)\), \((4,4)\) in \({\mathbb{R}}^2\).

We want to fit the line \(y_{{\bf a}}(x)=a_0+a_1x\) to the data-points. Define, as in theorem [thm:pseudoinverse-fit], \[X=\left(\begin{matrix} 1 & 1 \\ 1 & 2 \\ 1 & 3 \\ 1 & 4\end{matrix}\right), \qquad {\bf a}=\left(\begin{matrix}a_0 \\ a_1\end{matrix}\right), \qquad {\bf y}=\left(\begin{matrix}1 \\ 2.4 \\ 3.6 \\ 4\end{matrix}\right).\] Then \[X^tX=\left(\begin{matrix}4 & 10 \\ 10 & 30\end{matrix}\right) \Rightarrow \psi(X)=\frac{1}{10} \left(\begin{matrix}10 & 5 & 0 & -5\\ -3 & -1 & 1 & 3\end{matrix}\right).\] Thus \[{\bf a}=\psi(X){\bf y}= \left(\begin{matrix}0.2 \\ 1.02\end{matrix}\right),\] and so \(y_{{\bf a}}(x)=0.2+1.02x\) is the best linear (least-squares) fit to the data points.