Linear Algebra and Analysis

Explain why it is typically impossible to compute the upper triangular matrix whose existence is guaranteed by Schur’s theorem.
Now recall the QR factorization of Theorem 13.2.9 on Page 873. The QR algorithm is a technique which does compute the upper triangular matrix in Schur’s theorem sometimes. There is much more to the QR algorithm than will be presented here. In fact, what I am about to show you is not the way it is done in practice. One first obtains what is called a Hessenburg matrix for which the algorithm will work better. However, the idea is as follows. Start with A an n×n matrix having real eigenvalues. Form A = QR where Q is orthogonal and R is upper triangular. (Right triangular.) This can be done using the technique of Theorem 13.2.9 using Householder matrices. Next take A₁ ≡ RQ. Show that A = QA₁Q^T. In other words these two matrices, A,A₁ are similar. Explain why they have the same eigenvalues. Continue by letting A₁ play the role of A. Thus the algorithm is of the form A_n = QR_n and A_n+1 = R_n+1Q. Explain why A = Q_nA_nQ_n^T for some Q_n orthogonal. Thus A_n is a sequence of matrices each similar to A. The remarkable thing is that often these matrices converge to an upper triangular matrix T and A = QTQ^T for some orthogonal matrix, the limit of the Q_n where the limit means the entries converge. Then the process computes the upper triangular Schur form of the matrix A. Thus the eigenvalues of A appear on the diagonal of T. You will see approximately what these are as the process continues.
↑Try the QR algorithm on

$( ) - 1 - 2 6 6$

which has eigenvalues 3 and 2. I suggest you use a computer algebra system to do the computations.
↑Now try the QR algorithm on

$( 0 - 1 ) 2 0$

Show that the algorithm cannot converge for this example. Hint: Try a few iterations of the algorithm. Use a computer algebra system if you like.
↑Show the two matrices A ≡
( ) 0 − 1 4 0
and B ≡
( ) 0 − 2 2 0
are similar; that is there exists a matrix S such that A = S⁻¹BS but there is no orthogonal matrix Q such that Q^TBQ = A. Show the QR algorithm does converge for the matrix B although it fails to do so for A.
Let F be an m × n matrix. Show that F^∗F has all real eigenvalues and furthermore, they are all nonnegative.
If A is a real n × n matrix and λ is a complex eigenvalue λ = a + ib,b≠0, of A having eigenvector z + iw, show that w≠0.
Suppose A = Q^TDQ where Q is an orthogonal matrix and all the matrices are real. Also D is a diagonal matrix. Show that A must be symmetric.
Suppose A is an n × n matrix and there exists a unitary matrix U such that

$A = U *DU$

where D is a diagonal matrix. Explain why A must be normal.
If A is Hermitian, show that det
(A )
must be real.

Show that every unitary matrix preserves distance. That is, if U is unitary,

|Ux| = |x|.

Show that if a matrix does preserve distances, then it must be unitary.
↑Show that a complex normal matrix A is unitary if and only if its eigenvalues have magnitude equal to 1.
Suppose A is an n × n matrix which is diagonally dominant. Recall this means

$\sum |aij| < |aii| j⁄=i$

show A⁻¹ must exist.

Give some disks in the complex plane whose union contains all the eigenvalues of the matrix

( ) 1 + 2i 4 2 |( 0 i 3 |) 5 6 7

Show a square matrix is invertible if and only if it has no zero eigenvalues.
Using Schur’s theorem, show the trace of an n×n matrix equals the sum of the eigenvalues and the determinant of an n × n matrix is the product of the eigenvalues.
Using Schur’s theorem, show that if A is any complex n × n matrix having eigenvalues
{λi}
listed according to multiplicity, then ∑ _i,j
|Aij|
² ≥∑ _i=1ⁿ
|λi|
². Show that equality holds if and only if A is normal. This inequality is called Schur’s inequality. [25]

Here is a matrix.

( ) | 1234 6 5 3 | || 0 - 654 9 123 || ( 98 123 10,000 11 ) 56 78 98 400

I know this matrix has an inverse before doing any computations. How do I know?

Show the critical points of the following function are

$( ) (0,- 3,0),(2,- 3,0),and 1,- 3,- 1 3$

and classify them as local minima, local maxima or saddle points.
f
(x,y,z)
= −
32
x⁴ + 6x³ − 6x² + zx² − 2zx − 2y² − 12y − 18 −
32
z².
Here is a function of three variables.

$2 2 2 f (x,y,z) = 13x + 2xy + 8xz + 13y + 8yz + 10z$

change the variables so that in the new variables there are no mixed terms, terms involving xy,yz etc. Two eigenvalues are 12 and 18.

Here is a function of three variables.

f (x,y,z) = 2x2 - 4x + 2+ 9yx - 9y- 3zx+ 3z +5y2 - 9zy - 7z2

change the variables so that in the new variables there are no mixed terms, terms involving xy,yz etc. The eigenvalues of the matrix which you will work with are −

,−1.

Here is a function of three variables.

$f (x,y,z) = - x2 + 2xy + 2xz - y2 + 2yz - z2 +x$

change the variables so that in the new variables there are no mixed terms, terms involving xy,yz etc.

Show the critical points of the function,

f (x,y,z) = - 2yx2 - 6yx - 4zx2 - 12zx + y2 + 2yz.

are points of the form,

(x,y,z) = (t,2t2 + 6t,- t2 - 3t)

for t ∈ ℝ and classify them as local minima, local maxima or saddle points.

Show the critical points of the function

1 1 f (x,y,z) = -x4 - 4x3 + 8x2 - 3zx2 + 12zx+ 2y2 + 4y +2 +-z2. 2 2

are

, and

and classify them as local minima, local maxima or saddle points.

Let f
(x,y)
= 3x⁴ − 24x² + 48 − yx² + 4y. Find and classify the critical points using the second derivative test.
Let f
(x,y)
= 3x⁴ − 5x² + 2 − y²x² + y². Find and classify the critical points using the second derivative test.
Let f
(x,y)
= 5x⁴ − 7x² − 2 − 3y²x² + 11y² − 4y⁴. Find and classify the critical points using the second derivative test.
Let f
(x,y,z)
= −2x⁴ − 3yx² + 3x² + 5x²z + 3y² − 6y + 3 − 3zy + 3z + z². Find and classify the critical points using the second derivative test.
Let f
(x,y,z)
= 3yx² − 3x² −x²z −y² + 2y − 1 + 3zy − 3z − 3z². Find and classify the critical points using the second derivative test.
Let Q be orthogonal. Find the possible values of det
(Q )
.
Let U be unitary. Find the possible values of det
(U )
.
If a matrix is nonzero can it have only zero for eigenvalues?
A matrix A is called nilpotent if A^k = 0 for some positive integer k. Suppose A is a nilpotent matrix. Show it has only 0 for an eigenvalue.
If A is a nonzero nilpotent matrix, show it must be defective.
Suppose A is a nondefective n × n matrix and its eigenvalues are all either 0 or 1. Show A² = A. Could you say anything interesting if the eigenvalues were all either 0,1,or −1? By DeMoivre’s theorem, an n^th root of unity is of the form

$( (2kπ-) ( 2kπ) ) cos n +isin n$

Could you generalize the sort of thing just described to get Aⁿ = A? Hint: Since A is nondefective, there exists S such that S⁻¹AS = D where D is a diagonal matrix.

This and the following problems will present most of a differential equations course. Most of the explanations are given. You fill in any details needed. To begin with, consider the scalar initial value problem

' y = ay,y(t0) = y0

When a is real, show the unique solution to this problem is y = y₀e^a

. Next suppose

y' = (a+ ib)y,y(t0) = y0 (14.6)

(14.6)

where y

= u

+ iv

. Show there exists a unique solution and it is given by y

a(t-t0) (a+ib)(t-t0) y0e (cosb(t- t0) +isinb(t- t0)) \equiv e y0. (14.7)

(14.7)

Next show that for a real or complex there exists a unique solution to the initial value problem

y' = ay + f,y(t0) = y0

and it is given by

\int t y(t) = ea(t-t0)y0 + eat e- asf (s)ds. t0

Hint: For the first part write as y^′−ay = 0 and multiply both sides by e^−at. Then explain why you get

d-(e-aty(t)) = 0,y (t) = 0. dt 0

Now you finish the argument. To show uniqueness in the second part, suppose

y' = (a + ib)y,y (t ) = 0 0

and verify this requires y

= 0. To do this, note

y' = (a - ib)y,y-(t0) = 0

and that

= 0 and

d-|y (t)|2 = y'(t)y-(t)+ y'(t)y (t) dt

= (a+ ib)y(t)y(t) +(a - ib)y(t)y(t) = 2a|y(t)|2.

Thus from the first part

² = 0e^−2at = 0. Finally observe by a simple computation that 14.6 is solved by 14.7. For the last part, write the equation as

' y - ay = f

and multiply both sides by e^−at and then integrate from t₀ to t using the initial condition.

Now consider A an n × n matrix. By Schur’s theorem there exists unitary Q such that

Q-1AQ = T

where T is upper triangular. Now consider the first order initial value problem

x' = Ax, x(t0) = x0.

Show there exists a unique solution to this first order system. Hint: Let y = Q⁻¹x and so the system becomes

y' = Ty,y (t0) = Q -1x0 (14.8)

(14.8)

Now letting y =

^T, the bottom equation becomes

( ) y'n = tnnyn,yn (t0) = Q -1x0 . n

Then use the solution you get in this to get the solution to the initial value problem which occurs one level up, namely

( ) y'n-1 = t(n- 1)(n-1)yn-1 +t(n-1)nyn,yn-1(t0) = Q-1x0 n-1

Continue doing this to obtain a unique solution to 14.8.

Now suppose Φ

is an n × n matrix of the form

( ) Φ(t) = x1(t) \cdot\cdot\cdot xn(t) (14.9)

(14.9)

where

x'k(t) = Axk (t).

Explain why

Φ'(t) = AΦ (t)

if and only if Φ

is given in the form of 14.9. Also explain why if c ∈ Fⁿ,y

≡ Φ

c solves the equation y^′

= Ay

In the above problem, consider the question whether all solutions to
$' x = Ax (14.10)$ (14.10)

are obtained in the form Φ
(t)
c for some choice of c ∈ Fⁿ. In other words, is the general solution to this equation Φ
(t)
c for c ∈ Fⁿ? Prove the following theorem using linear algebra.

Theorem 14.5.1 Suppose Φ
(t)
is an n × n matrix which satisfies Φ^′
(t)
= AΦ
(t)
. Then the general solution to 14.10 is Φ
(t)
c if and only if Φ
(t)
⁻¹ exists for some t. Furthermore, if Φ^′
(t)
= AΦ
(t)
, then either Φ
(t)
⁻¹ exists for all t or Φ
(t)
⁻¹ never exists for any t.

(det
(Φ(t))
is called the Wronskian and this theorem is sometimes called the Wronskian alternative.)
Hint: Suppose first the general solution is of the form Φ
(t)
c where c is an arbitrary constant vector in Fⁿ. You need to verify Φ
(t)
⁻¹ exists for some t. In fact, show Φ
(t)
⁻¹ exists for every t. Suppose then that Φ
(t0)
⁻¹ does not exist. Explain why there exists c ∈ Fⁿ such that there is no solution x to the equation c = Φ
(t0)
x. By the existence part of Problem 38 there exists a solution to

$x' = Ax, x(t0) = c$

but this cannot be in the form Φ
(t)
c. Thus for every t, Φ
(t)
⁻¹ exists. Next suppose for some t₀,Φ
(t0)
⁻¹ exists. Let z^′ = Az and choose c such that

$z (t0) = Φ (t0)c$

Then both z
(t)
,Φ
(t)
c solve

$' x = Ax, x(t0) = z(t0)$

Apply uniqueness to conclude z = Φ
(t)
c. Finally, consider that Φ
(t)
c for c ∈ Fⁿ either is the general solution or it is not the general solution. If it is, then Φ
(t)
⁻¹ exists for all t. If it is not, then Φ
(t)
⁻¹ cannot exist for any t from what was just shown.

Let Φ^′

= AΦ

. Then Φ

is called a fundamental matrix if Φ

⁻¹ exists for all t. Show there exists a unique solution to the equation

' x = Ax + f,x(t0) = x0 (14.11)

(14.11)

and it is given by the formula

\int t x (t) = Φ (t)Φ(t0)- 1x0 + Φ (t) Φ (s)-1 f (s)ds t0

Now these few problems have done virtually everything of significance in an entire undergraduate differential equations course, illustrating the superiority of linear algebra. The above formula is called the variation of constants formula.

Hint: Uniquenss is easy. If x₁,x₂ are two solutions then let u

= x₁

− x₂

and argue u^′ = Au,u

= 0. Then use Problem 38. To verify there exists a solution, you could just differentiate the above formula using the fundamental theorem of calculus and verify it works. Another way is to assume the solution in the form

x(t) = Φ (t)c(t)

and find c

to make it all work out. This is called the method of variation of parameters.

Show there exists a special Φ such that Φ^′
(t)
= AΦ
(t)
,Φ
(0)
= I, and suppose Φ
(t)
⁻¹ exists for all t. Show using uniqueness that

$Φ(- t) = Φ(t)-1$

and that for all t,s ∈ ℝ

$Φ(t+ s) = Φ (t) Φ(s)$

Explain why with this special Φ, the solution to 14.11 can be written as

$\int t x (t) = Φ (t- t0)x0 + t0 Φ(t- s)f (s)ds.$

Hint: Let Φ
(t)
be such that the j^th column is x_j
(t)
where

$x'j = Axj,xj (0) = ej.$

Use uniqueness as required.

You can see more on this problem and the next one in the latest version of Horn and Johnson, [19]. Two n × n matrices A,B are said to be congruent if there is an invertible P such that

B = P AP *

Let A be a Hermitian matrix. Thus it has all real eigenvalues. Let n₊ be the number of positive eigenvalues, n₋, the number of negative eigenvalues and n₀ the number of zero eigenvalues. For k a positive integer, let I_k denote the k × k identity matrix and O_k the k × k zero matrix. Then the inertia matrix of A is the following block diagonal n × n matrix.

( ) | In+ | ( In- ) On0

Show that A is congruent to its inertia matrix. Next show that congruence is an equivalence relation on the set of Hermitian matrices. Finally, show that if two Hermitian matrices have the same inertia matrix, then they must be congruent. Hint: First recall that there is a unitary matrix, U such that

( ) Dn+ U*AU = |( Dn- |) O n0

where the D_n₊ is a diagonal matrix having the positive eigenvalues of A, D_n₋ being defined similarly. Now let

denote the diagonal matrix which replaces each entry of D_n₋ with its absolute value. Consider the two diagonal matrices

( ) D -n1+∕2 D = D* = |( || ||-1∕2 |) Dn- In0

Now consider D^∗U^∗AUD.

Show that if A,B are two congruent Hermitian matrices, then they have the same inertia matrix. Hint: Let A = SBS^∗ where S is invertible. Show that A,B have the same rank and this implies that they are each unitarily similar to a diagonal matrix which has the same number of zero entries on the main diagonal. Therefore, letting V _A be the span of the eigenvectors associated with positive eigenvalues of A and V _B being defined similarly, it suffices to show that these have the same dimensions. Show that
(Ax, x)
> 0 for all x ∈ V _A. Next consider S^∗V _A. For x ∈ V _A, explain why
$( ) (BS *x,S*x) = S-1A (S*)-1S*x,S*x ( ) ( ( )* ) = S-1Ax,S*x = Ax, S -1 S*x = (Ax, x) > 0$
Next explain why this shows that S^∗V _A is a subspace of V _B and so the dimension of V _B is at least as large as the dimension of V _A. Hence there are at least as many positive eigenvalues for B as there are for A. Switching A,B you can turn the inequality around. Thus the two have the same inertia matrix.
Let A be an m × n matrix. Then if you unraveled it, you could consider it as a vector in ℂ^nm. The Frobenius inner product on the vector space of m × n matrices is defined as

$(A,B) \equiv trace(AB *)$

Show that this really does satisfy the axioms of an inner product space and that it also amounts to nothing more than considering m × n matrices as vectors in ℂ^nm.
↑Consider the n × n unitary matrices. Show that whenever U is such a matrix, it follows that

$-- |U |ℂnn = \sqrt n$

Next explain why if
{Uk }
is any sequence of unitary matrices, there exists a subsequence
{Uk } m
_m=1^∞ such that lim_m→∞U_{k_m} = U where U is unitary. Here the limit takes place in the sense that the entries of U_{k_m} converge to the corresponding entries of U.

↑Let A,B be two n × n matrices. Denote by σ

the set of eigenvalues of A. Define

dist(σ (A ),σ(B)) = λm\inaσx(A)min{|λ- μ | : μ \in σ (B )}

Explain why dist

is small if and only if every eigenvalue of A is close to some eigenvalue of B. Now prove the following theorem using the above problem and Schur’s theorem. This theorem says roughly that if A is close to B then the eigenvalues of A are close to those of B in the sense that every eigenvalue of A is close to an eigenvalue of B. This is a very important observation when you try to approximate eigenvalues using the QR algorithm.

Theorem 14.5.2 Suppose lim_k→∞A_k = A. Then

kli\tom\infty dist(σ(Ak),σ (A )) = 0

Let A =
( ) a b c d
be a 2 × 2 matrix which is not a multiple of the identity. Show that A is similar to a 2 × 2 matrix which has at least one diagonal entry equal to 0. Hint: First note that there exists a vector a such that Aa is not a multiple of a. Then consider

$( )-1 ( ) B = a Aa A a Aa$

Show B has a zero on the main diagonal.
↑ Let A be a complex n × n matrix which has trace equal to 0. Show that A is similar to a matrix which has all zeros on the main diagonal. Hint: Use Problem 39 on Page 257 to argue that you can say that a given matrix is similar to one which has the diagonal entries permuted in any order desired. Then use the above problem and block multiplication to show that if the A has k nonzero entries, then it is similar to a matrix which has k − 1 nonzero entries. Finally, when A is similar to one which has at most one nonzero entry, this one must also be zero because of the condition on the trace.

↑An n × n matrix X is a commutator if there are n × n matrices A,B such that X = AB − BA. Show that the trace of any commutator is 0. Next show that if a complex matrix X has trace equal to 0, then it is in fact a commutator. Hint: Use the above problem to show that it suffices to consider X having all zero entries on the main diagonal. Then define

( ) 1 0 { || 2 || Xij-if i ⁄= j A = || .. || , Bij = i-j ( . ) 0 if i = j 0 n

Linear Algebra and Analysis

14.5 Exercises