An Inquiry-Based Introduction to Linear Algebra and Applications

Subsection Application: The Gershgorin Disk Theorem

We have now seen different methods for calculating/approximating eigenvalues of a matrix. The algebraic method using the characteristic polynomial can provide exact values, but only in cases where the size of the matrix is small. Methods like the power method allow us to approximate eigenvalues in many, but not all, cases. These approximation techniques can be made more efficient if we have some idea of where the eigenvalues are. The Gershgorin Disc Theorem is a useful tool that can quickly provide bounds on the location of eigenvalues using elementary calculations. For example, using the Gershsgorin Disk Theorem we can quickly tell that the real parts of the eigenvalues of the matrix

lie between \(-4\) and 5 and the imaginary parts lie between \(-5\) and 2. Even more, we can say that the eigenvalues lie in the disks (called Gershgorin disks) shown in Figure 21.1.

We will learn more details about the Gershgorin Disk Theorem at the end of this section.

Subsection Introduction

So far we have worked with real matrices whose eigenvalues are all real. However, the characteristic polynomial of a matrix with real entries can have complex roots. In this section we investigate the properties of these complex roots and their corresponding eigenvectors, how these complex eigenvectors are found, and the geometric interpretation of the transformations defined by matrices with complex eigenvalues. Although we can consider matrices that have complex numbers as entries, we will restrict ourselves to matrices with real entries.

Subsection Complex Eigenvalues

As you noticed in Preview Activity 21.1, the complex roots of the characteristic equation of a real matrix \(A\) come in complex conjugate pairs. This should come as no surprise since we know through our use of the quadratic formula that complex roots of (real) quadratic polynomials come in complex conjugate pairs. More generally, if \(p(x)=a_0+a_1x+a_2x^2 + \cdots + a_nx^n\) is a polynomial with real coefficients and \(z\) is a root of this polynomial, meaning \(p(z)=0\text{,}\) then

Therefore, \(\overline{z}\) is also a root of \(p(x)\text{.}\)

In Preview Activity 21.1 and in Activity 21.2, you found that if \(\vv\) is an eigenvector of \(A\) corresponding to \(\lambda\text{,}\) then \(\overline{\vv}\) obtained by taking the complex conjugate of each entry in \(\vv\) is an eigenvector of \(A\) corresponding to \(\overline{\lambda}\text{.}\) Specifically, if \(\vv=\vu+i\vw\) where both \(\vu\) and \(\vw\) are real vectors is an eigenvector of \(A\text{,}\) then so is \(\overline{\vv} = \vu-i\vw\text{.}\) We can justify this property using matrix algebra as follows:

In the first equality, we used the fact that \(A\) is a real matrix, so \(\overline{A}=A\text{.}\) In all the other equalities, we used the properties of the conjugation operation in complex numbers.

Subsection Rotation and Scaling Matrices

Recall that a rotation matrix is of the form

where the rotation is counterclockwise about the origin by an angle of \(\theta\) radians. In Activity 21.2, we considered the rotation matrix with angle \(\pi/2\) in counterclockwise direction. We will soon see that rotation matrices play an important role in the geometry of a matrix transformation for a matrix that has complex eigenvalues. In this activity, we will restrict ourselves to the \(2 \times 2\) case, but similar arguments can be made in higher dimensions.

More generally, if we have a matrix \(A\) of the form \(A=\left[ \begin{array}{cr} a\amp -b \\ b\amp a \end{array} \right]\text{,}\) then

The first matrix in the decomposition is a scaling matrix with a scaling factor of \(s=\sqrt{a^2+b^2}\text{.}\) So if \(s>1\text{,}\) the transformation stretches vectors, and if \(s\lt 1\text{,}\) the transformation shrinks vectors. The second matrix in the decomposition is a rotation matrix with angle \(\theta\) such that \(\cos(\theta)=\frac{a}{\sqrt{a^2+b^2}}\) and \(\sin(\theta)=\frac{b}{\sqrt{a^2+b^2}}\text{.}\) This angle is also the angle between the positive \(x\)-axis and the vector \(\vv=\left[ \begin{array}{c} a\\ b \end{array} \right]\text{.}\) We will refer to the matrices of the form \(\left[ \begin{array}{cr} a\amp -b \\ b\amp a \end{array} \right]\) as rotation-scaling matrices.

Subsection Matrices with Complex Eigenvalues

Now we will investigate how a general \(2\times 2\) matrix with complex eigenvalues can be seen to be similar (both in a linear algebra and a colloquial meaning) to a rotation-scaling matrix.

In Activity 21.4, we saw that the matrix \(B\) with complex eigenvalues \(2\pm 3i\) is similar to a rotation-scaling matrix. Specifically \(R=P^{-1}BP\text{,}\) where the columns of \(P\) are the real and imaginary parts of an eigenvector of \(B\text{,}\) is the rotation-scaling matrix with a factor of scaling by \(\sqrt{2^2+3^2}\) and a rotation by angle \(\theta=\arccos(\frac{2}{\sqrt{2^2+3^2}})\text{.}\)

Does a similar decomposition result hold for a general \(2\times 2\) matrix with complex eigenvalues? We investigate this question in the next activity.

Your work in Activity 21.5 shows that any \(2\times 2\) matrix is similar to a rotation-scaling matrix with a factor of scaling by \(\sqrt{a^2+b^2}\) and a rotation by angle \(\theta=\arccos(\frac{a}{\sqrt{a^2+b^2}})\) if \(b\geq 0\text{,}\) and \(\theta=-\arccos(\frac{a}{\sqrt{a^2+b^2}})\) if \(b\lt 0\text{.}\) Geometrically, this means that every \(2 \times 2\) real matrix with complex eigenvalues is just a scaled rotation (\(R\)) with respect to the basis \(\B\) formed by \(\vu\) and \(\vw\) from the complex eigenvector \(\vv\text{.}\) Multiplying by \(P^{-1}\) and \(P\) simply provides the change of basis from the standard basis to the basis \(\B\text{,}\) as we will see in detail when we learn about linear transformations.

The one fact that we have not yet addressed is why the matrix \(P = [ \vu \ \vw ]\) is invertible. We do that now to complete the argument.

Let \(A\) be a real \(2 \times 2\) matrix with \(A \vv = \lambda \vv\text{,}\) where \(\lambda = a-bi\text{,}\) \(b \neq 0\) and \(\vv=\vu+i\vw\) (where \(\vu\) and \(\vv\) are in \(\R^2\)) with \(\vw \neq \vzero\text{.}\) From Activity 21.5 we know that

To show that \(\vu\) and \(\vw\) are linearly independent, we need to show that no nontrivial linear combination of \(\vu\) and \(\vw\) can be the zero vector. Suppose

for some scalars \(x_1\) and \(x_2\text{.}\) We will show that \(x_1 = x_2 = 0\text{.}\) Assume to the contrary that one of \(x_1, x_2\) is not zero. First, assume \(x_1 \neq 0\text{.}\) Then \(\vu = -\frac{x_2}{x_1} \vw\text{.}\) Let \(c = -\frac{x_2}{x_1}\text{.}\) From this we have

Since \(\vw \neq \vzero\) we must have \((a+cb)c = ca-b\text{.}\) A little algebra shows that \((c^2+1)b = 0\text{.}\) Since \(b \neq 0\text{,}\) we conclude that \(c^2+1=0\text{,}\) which is impossible for a real constant \(c\text{.}\) Therefore, we cannot have \(x_1 \neq 0\text{.}\) A similar argument (left to the reader) shows that \(x_2 = 0\text{.}\) Thus we can conclude that \(\vu\) and \(\vw\) are linearly independent.

Subsection Examples

What follows are worked examples that use the concepts from this section.

Subsection Summary

• For a real matrix, complex eigenvalues appear in conjugate pairs. Specifically, if \(\lambda=a+ib\) is an eigenvalue of a real matrix \(A\text{,}\) then \(\overline{\lambda}=a-ib\) is also an eigenvalue of \(A\text{.}\)

• For a real matrix, if a \(\vv\) is an eigenvector corresponding to \(\lambda\text{,}\) then the vector \(\overline{\vv}\) obtained by taking the complex conjugate of each entry in \(\vv\) is an eigenvector corresponding to \(\overline{\lambda}\text{.}\)

• The rotation-scaling matrix \(A=\left[ \begin{array}{cr} a\amp -b \\ b\amp a \end{array} \right]\) can be written as

  \begin{equation*} \left[ \begin{array}{cc} \sqrt{a^2+b^2} \amp 0 \\ 0\amp \sqrt{a^2+b^2} \end{array} \right] \left[ \begin{array}{cc} \frac{a}{\sqrt{a^2+b^2}}\amp \frac{-b}{\sqrt{a^2+b^2}} \\ \frac{b}{\sqrt{a^2+b^2}}\amp \frac{a}{\sqrt{a^2+b^2}} \end{array} \right] \,\text{.} \end{equation*}

  This decomposition geometrically means that the transformation corresponding to \(A\) can be viewed as a rotation by angle \(\theta=\arccos\left(\frac{a}{\sqrt{a^2+b^2}}\right)\) if \(b\geq 0\text{,}\) or \(\theta=-\arccos\left(\frac{a}{\sqrt{a^2+b^2}}\right)\) if \(b\lt 0\text{,}\) followed by a scaling by factor \(\sqrt{a^2+b^2}\text{.}\)

• If \(A\) is a real \(2\times 2\) matrix with complex eigenvalue \(a-bi\) and corresponding eigenvector \(\vv=\vu+i\vw\text{,}\) then \(A\) is similar to the rotation-scaling matrix \(R=\left[ \begin{array}{cr} a\amp -b \\ b\amp a \end{array} \right]\text{.}\) More specifically,

  \begin{equation*} A=PRP^{-1} \; , \text{ where } P=[ \vu \ \vw ]\,\text{.} \end{equation*}

Subsection Project: Understanding the Gershgorin Disk Theorem

To understand the Gershgorin Disk Theorem, we need to recall how to visualize a complex number in the plane. Recall that a complex number \(z\) is a number of the form \(z = a+bi\) where \(a\) and \(b\) are real numbers and \(i^2 = -1\text{.}\) The number \(a\) is the real part of \(z\text{,}\) denoted as \(\text{ Re } (z)\text{,}\) and \(b\) is the imaginary part of \(z\text{,}\) denoted \(\text{ Im } (z)\text{.}\) The set of all complex numbers is denoted \(\C\text{.}\) We define addition and multiplication on \(\C\) as follows. For \(a+bi, c+di \in \C\text{,}\)

Note that the product is what we would expect if we “expanded” the product in the normal way and used the fact that \(i^2=-1\text{.}\) The set of complex numbers forms a field — that is, \(\C\) satisfies all of the same properties as \(\R\) as stated in Theorem 4.3.

We can visualize the complex number \(a+bi\) in the plane as the point \((a,b)\text{.}\) Here we are viewing the horizontal axis as the real axis and the vertical axis as the imaginary axis. The length (or magnitude) of the complex number \(z = a+bi\text{,}\) which we denote as \(|z|\text{,}\) is the distance from the origin to \(z\text{.}\) So by the Pythagorean Theorem we have \(|a+bi| = \sqrt{a^2+b^2}\text{.}\) Note that the magnitude of \(z = a+bi\) can be written as a complex product

The complex number \(a-bi\) is called the complex conjugate of \(z=a+bi\) and is denoted as \(\overline{z}\text{.}\) A few important properties of real numbers and their conjugates are the following. Let \(z = a+bi\) and \(w = c+di\) be complex numbers. Then

• \(\overline{z+w} = \overline{(a+c) + (b+d)i} = (a+c)-(b+d)i = (a-bi) + (c-di) = \overline{z} + \overline{w}\text{,}\)

• \(\overline{zw} = \overline{(ac-bd) + (ad+bc)i} = (ac-bd)-(ad+bc)i = (a-bi)(c-di) = \overline{z} \overline{w}\text{,}\)

• \(\overline{\overline{z}} = z\text{,}\)

• \(|z| = \sqrt{a^2+b^2} \geq \sqrt{a^2} = |a| = |\text{ Re } (z)|\text{,}\)

• \(|z| = \sqrt{a^2+b^2} \geq \sqrt{b^2} = |b| = |\text{ Im } (z)|\text{,}\)

• \(\left| \overline{z} \right| = |z|\text{,}\)

• \(|z| = 0\) if and only if \(z = 0\text{,}\)

• If \(p(x)\) is a polynomial with real coefficients and the complex number \(z\) satisfies \(p(z) = 0\text{,}\) then \(p\left(\overline{z}\right) = 0\) as well.

Using these facts we can show that the triangle inequality is true for complex numbers. That is,

To see why, notice that

Since \(|z+w|\text{,}\) \(|z|\text{,}\) and \(|w|\) are all non-negative, taking square roots of both sides gives us \(|z+w| \leq |z| + |w|\) as desired. We can extend this triangle inequality to any number of complex numbers. That is, if \(z_1\text{,}\) \(z_2\text{,}\) \(\ldots\text{,}\) \(z_k\) are complex numbers, then

We can prove Equation (21.1) by mathematical induction. We have already done the \(k=2\) case and so we assume that Equation (21.1) is true for any sum of \(k\) complex numbers. Now suppose that \(z_1\text{,}\) \(z_2\text{,}\) \(\ldots\text{,}\) \(z_k\text{,}\) \(z_{k+1}\) are complex numbers. Then

To prove the Gershgorin Disk Theorem, we will use the Levy-Desplanques Theorem, which gives conditions that guarantee that a matrix is invertible. We illustrate with an example in the following activity.

What makes the arguments work in Project Activity 21.6 is that \(|3| > |2|\) and \(|4| > |-1|\text{.}\) This argument can be extended to larger matrices, as described in the following theorem.

Any matrix \(A = [a_{ij}]\) satisfying the condition of the Levy-Desplanques Theorem is given a special name.

So any strictly diagonally dominant matrix is invertible. A quick glance can show that a matrix is strictly diagonally dominant. For example, since \(|3| > |1| + |-1|\text{,}\) \(|12| > |5| +|6|\text{,}\) and \(|-8| > |-2| + |4|\text{,}\) the matrix

is strictly diagonally dominant and therefore invertible. However, just because a matrix is not strictly diagonally dominant, it does not follow that the matrix is non-invertible. For example, the matrix \(B = \left[ \begin{array}{cc} 1\amp 2 \\ 0\amp 1 \end{array} \right]\) is invertible, but not strictly diagonally dominant.

Now we can address the Gershgorin Disk Theorem.

The Gershgorin Disk Theorem has a consequence that gives additional information about the eigenvalues if some of the Gershgorin disks do not overlap.

Proof.

Most proofs of this theorem require some results from topology. For that reason, we will not present a completely rigorous proof but rather give the highlights. Let \(A = [a_{ij}]\) be an \(n \times n\) matrix. Let \(D_i\) be a collection of Gershgorin disks of \(A\) for \(1 \leq i \leq m\) such that \(S = \cup_{1 \leq i \leq m} D_i\) does not intersect any other Gershgorin disk of \(A\text{,}\) and let \(S'\) be the union of the Gershgorin disks of \(A\) that are different from the \(D_i\text{.}\) Note that \(S \cap S' = \emptyset\text{.}\) Let \(C\) be the matrix whose \(i\)th column is \(a_{ii}\ve_i\text{,}\) that is \(C\) is the diagonal matrix whose diagonal entries are the corresponding diagonal entries of \(A\text{.}\) Note that the eigenvalues of \(C\) are \(a_{ii}\) and the Gershgorin disks of \(C\) are just the points \(a_{ii}\text{.}\) So our theorem is true for this matrix \(C\text{.}\) To prove the result, we build a continuum of matrices from \(C\) to \(A\) as follows: let \(B = A-C\) (so that \(B\) is the matrix whose off-diagonal entries are those of \(A\) and whose diagonal entries are 0), and let \(A(t) = tB + C\) for \(t\) in the interval \([0,1]\text{.}\) Note that \(A(1) = A\text{.}\) Since the diagonal entries of \(A(t)\) are the same as those of \(A\text{,}\) the Gershgorin disks of \(A(t)\) have the same centers as the corresponding Gershgorin disks of \(A\text{,}\) while the radii of the Gershgorin disks of \(A(t)\) are those of \(A\) but scaled by \(t\text{.}\) So the Gershgorin disks of \(A(t)\) increase from points (the \(a_{ii}\)) to the Gershgorin disks of \(A\) as \(t\) increases from 0 to 1. While the centers of the disks all remain fixed, it is important to recognize that the eigenvalues of \(A(t)\) move as \(t\) changes. An illustration of this is shown in Figure 21.9 with the eigenvalues as the black points and the changing Gershgorin disks dashed in magenta, using the matrix \(\left[ \begin{array}{cc} i\amp \frac{1}{2} \\ 1\amp -2+i \end{array} \right]\text{.}\) We can learn about how the eigenvalues move with the characteristic polynomial.

Let \(p(t,x)\) be the characteristic polynomial of \(A(t)\text{.}\) Note that these characteristic polynomials are functions of both \(t\) and \(x\text{.}\) Since polynomials are continuous functions, their roots (the eigenvalues of \(A(t)\)) are continuous for \(t \in [0,1]\) as well. Let \(\lambda(t)\) be an eigenvalue of \(A(t)\text{.}\) Note that \(\lambda(1)\) is an eigenvalue of \(A\text{,}\) and \(\lambda(0)\) is one of the \(a_{ii}\) and is therefore in \(S\text{.}\) We will argue that \(\lambda(t)\) is in \(S\) for every value of \(t\) in \([0,1]\text{.}\) Let \(r_i\) be the radius of \(D_i\) and let \(D(t)_i\) be the Gershgorin disk of \(A(t)\) with the same center as \(D_i\) and radius \(r(t)_i = tr_i\text{.}\) Let \(S(t) = \cup_{1 \leq i \leq m} D(s)_i\text{.}\) Since \(r(s)_i \leq r_i\text{,}\) it follows that \(D(s)_i \subseteq D_i\) and so \(S(t) \cap S' = \emptyset\) as well. From topology, we know that since the disks \(D_i\) are closed, the union \(S\) of these disks is also closed. Similarly, \(S(t)\) and \(S'\) are closed. Thus, \(\lambda(t)\) is continuous in a closed set and so does not leave the set. Thus, \(\lambda(t)\) is in \(S\) for every value of \(t\) in \([0,1]\text{.}\)