Week 7 Self check questions and solutions

Week 7 Self check questions and solutions#

Question 1:

Let $A\in\mathbb{C}^{n\times n}$ be diagonalizable and $\lambda$ an eigenvalue of $A$ with associated right eigenvector $x$ and left eigenvector $y$. Consider the perturbed eigenvalue equation

\[ (A + \delta A)(x+ \delta x) = (\lambda + \delta \lambda)(x + \delta x). \]

To first order show that $|\delta\lambda| \leq \frac{\|x\| \|y\|}{|y^H\delta Ax|} \|\delta A\|$.

Solution:

We multiply out the perturbed eigenvalue equations and ignore higher order terms to obtain

\[ A\delta x + \delta A x = \lambda \delta x + \delta\lambda x. \]

We now multiply from the left with $y^H$ and use that $y^HA = \lambda y^H$, resulting in

\[ y^H\delta A x = \delta\lambda y^Hx, \]

from which we get

\[ \delta\lambda = \frac{y^H\delta A x}{y^Hx}. \]

Taking norms we obtain the bound

\[ |\delta\lambda|\leq \frac{\|x\| \|y\|}{|y^Hx|} \|\delta A\|. \]

This motivates the definition of the eigenvalue condition number $\kappa(\lambda)$ as

\[ \kappa(\lambda) = \frac{\|x\| \|y\|}{|y^Hx|}. \]

Question 2:

Let $A = \begin{bmatrix}a & c\\0 & b\end{bmatrix}$ for real numbers $a, b, c$ and $a\neq b$. Show that the condition numbers of the eigenvalues of $A$ asymptotically grow like $|\frac{c}{b-a}|$ as $b\rightarrow a$.

Solution:

The eigenvalues are $\lambda_1 = a$ and $\lambda_2=b$ with corresponding right/left eigenvectors $x_1 = \begin{bmatrix}1 & 0\end{bmatrix}^T$, $y_1 = \begin{bmatrix}-1 & \frac{c}{b-a}\end{bmatrix}^T$, $x_2 = \begin{bmatrix}\frac{c}{a-b} & -1\end{bmatrix}^T$, $y_2 = \begin{bmatrix}0 & 1\end{bmatrix}^T$.

The condition number of an eigenvalue is given as $\kappa = \frac{\|x\|_2\|y\|_2}{|x^Hy|}$. We hence obtain for both eigenpairs that

\[ \kappa = \left(1 + \frac{c^2}{(b-a)^2}\right)^{1/2}. \]

It follows that $\kappa\sim \left|\frac{c}{b-a}\right|$.

Question 3:

Show that the eigenvalues $\lambda$ of a Hermitian matrix are all real.

Solution:

Let $Ax= \lambda x$ for some eigenvalue $\lambda\in\mathbb{C}$ and $x\neq 0$ with $\|x\|_2=1$. Multiplying from the left with $x^H$ gives

\[ x^HAx = \lambda. \]

Taking the Hermitian transpose on both sides we obtain (taking into account that a Hermitian trans pose of a scalar is just its complex conjugate)

\[ x^HA^Hx = \overline{\lambda}. \]

Since $A=A^H$ it follows that $\lambda = \overline{\lambda}$ and therefore that $\lambda$ is real.

We can also proceed directly through the Schur decomposition. The Schur decomposition is $$ A = QR Q^T. $$

Since $A=A^H$ it follows that $R=R^H$. Since $R$ is upper triangular it must be therefore diagonal. Moreover, all the diagonal elements must be real since $R=R^H$. Since the eigenvalues are the diagonal elements it follows that the eigenvalues are real. The Schur decomposition is therefore identical to the eigenvalue decomposition $A= X\Lambda X^{-1}$ with $X=Q$ the matrix of eigenvectors.

Question 4:

Show that for a Hermitian matrix $A\in\mathbb{C}^{n\times n}$ we have

\[ x^HAx \in\mathbb{R} \]

for all $x\in\mathbb{C}^{n}$. A Hermitian matrix is called positive definite if in addition $x^HAx> 0$ for all $x\in\mathbb{C}^{n}\backslash\{0\}$. Show that this is equivalent to the condition that all eigenvalues of $A$ are positive. Finally, conclude that for a Hermitian positive definite matrix it holds that $\det(A) > 0$.

Solution:

$A$ is Hermitian, hence $A=A^H$ and therefore for the complex conjugate $\overline{x^HAx}$ of $x^HAx$ we have

\[ \overline{x^HAx} = \left(x^HAx\right)^H = x^HA^Hx = x^HAx. \]

Hence, $\overline{x^HAx} = x^HAx$ and therefore $x^HAx$ must be real for any complex vector $x\in\mathbb{C}^n$. It follows easily that if $A$ is Hermitian positive definite (that is $x^HAx>0$ for all $x\neq 0$) all eigenvalues are positive. Let $\lambda_j$ be an eigenvalue with associated eigenvector $x_j$ and $\|x_j\|_2 = 1$. We have that

\[ \lambda_j = x_j^HAx_j > 0 \]

since the condition that $x^HAx$ is positive holds for all nonzero vectors, and therefore in particular also eigenvectors.

Now assume that all eigenvalues $\lambda_j$ are larger than zero. Let $x\in\mathbb{C}$. We expand $x$ in the basis of eigenvectors and obtain $x = \sum_j \alpha_jx_j$. Assuming without loss of generality that $\|x_j\|_2=1$ for all $j$ we have from the orthogonality of eigenvectors for Hermitian matrices that

\[ x^HAx = \sum_j\lambda_j|\alpha_j|^2 > 0. \]

Finally, the determinant of a matrix is just the product of its eigenvalues. We hence obtain that $\det(A) > 0$ if $A$ is Hermitian positive definite.