Training camp for the IMC: linear algebra

Nanyang Technological University

4 Jun 2019

1 Theory
Jordan Canonical Form
Generalized eigenvectors: A vector e is a generalized eigenvector or a root vector of a linear operator
A : V → V if (A − λI)m e = 0. The minimal possible such m is called e’s height. In particular, generalized
eigenvectors of height 1 are eigenvectors. The root subspace Vλ consists of all root vectors corresponding
to an eigenvalue λ. It is the union of the ascending chain of kernels
ker(A − λI) ⊂ ker(A − λI)2 ⊂ · · ·

Canonical form: A Jordan block is a matrix with λ on the diagonal and 1 on the super-diagonal, that
is,  
λ 1 0 ··· 0 0
 0 λ 1
 ··· 0 0  
 0 0 λ ··· 0 0 
J= . . .
 
 .. .. .. .. .. .. 
 . . . 
 0 0 0 ··· λ 1 
0 0 0 ··· 0 λ
The canonical form is a block-diagonal matrix with Jordan blocks on the diagonal. It is unique up to
permutation of blocks and is a complete invariant of the conjugacy class. It always exists if vector space
is over algebraically closed field like C.

Minimal polynomial The minimal polynomial is the monic polynomial

µ A ( t ) = t k + a k −1 t k −1 + · · · + a 0
of the minimal degree which vanishes on A, i.e.
µ A ( A ) = A k + a k −1 · A k −1 + · · · + a 0 · I = 0
Properties:
• For any polynomial p(t), if p( A) = 0, then p is divisible by µ A .
• The characteristic polynomial χ A is divisible by µ A (which follows from the Cayley–Hamilton The-
orem).
• The minimal polynomial can be found from the Jordan form.

1
Size of Jordan blocks: The algebraic multiplicity of an eigenvalue λ is the total dimension of all Jordan
blocks with λ on the diagonal. The geometric multiplicity of an eigevalue λ, i.e., the dimension of the
eigenspace, is the number of Jordan blocks.

Rational Canonical Form Any square matrix T has a canonical form without any need to extend the
field of its coefficients. There exists an invertible matrix Q such that

Q−1 TQ = diag [ L(ψ1 ), L(ψ2 ), . . . , L(ψs )] ,

called the rational canonical form, where L( f ) is the companion matrix

 
0 0 ···
0 0 − a0

 1 0 ···
0 0 − a1 

 0 0 ···
1 0 − a2 
L( f ) = 
 
.. ..
.. . . .. .. 

 . .. . . . 

 0 0 0 ··· 0 − a n −2 
0 0 0 ··· 1 − a n −1

of the monic polynomial f ( x ) = a0 + a1 x + · · · + an−1 x n−1 + x n . The polynomials ψi are called the “in-
variant factors” of T and satisfy ψi |ψi+1 for i = 1, . . . , s − 1 (Hatwing 1996). The polynomial ψs is the
matrix minimal polynomial and the product ∏ ψi is the characteristic polynomial of T.

Corollary 1 If two matrices with entries in the field F are conjugate over a bigger field K ⊃ F, then they are
conjugate over F as well.

Cauchy-Binnet formula
Let A be an m × n matrix and B be an n × m matrix (n ≥ m). Write [n] for the set {1, . . . , n}, and ([m
n]
) for
n [n]
the set of all m-combinations of [n] (there are (m) of them). For S ∈ ( m ) we write A[m],S for the m × m
matrix whose columns are the columns of A at indices from S, and BS,[m] for the m × m matrix whose
rows are the rows of B at indices from S.
Then    
det ( AB) = ∑ det A[m],S det BS,[m] .
S∈([m
n]
)

Pfaffian
Let A be a 2n × 2n anti-symmetric matrix (A + A T = 0). Then det ( A) is a perfect square and pf( A)2 =
det( A).
Formula
n
1
2 n! σ∈∑ ∏ aσ(2i−1),σ(2i) .
pf( A) = n sgn ( σ )
S i =1
2n

One can associate to any skew-symmetric 2n × 2n matrix A = [ aij ] a bivector ω = ∑i< j aij ei ∧ e j ,
where {e1 , e2 , . . . , e2n } is the standard basis of R2n . The Pfaffian is then defined by the equation
1 n 1 2 2n n
n! ω = pf( A ) e ∧ e ∧ · · · ∧ e , here ω denotes the wedge product of n copies of ω with itself. If
A = [ A1 , A2 . . . , An ] then det ( A) = A1 ∧ A2 ∧ · · · ∧ An .
2 Problem Set
Question 1.
Prove that if A is (2n + 1) × (2n + 1) anti-symmetric matrix (A T = − A) then det ( A) = 0.

Question 2.
1. Let A be a symmetric matrix such that the sum of its columns is 0. Prove that the minor Mii of the
matrix A does not depend on the choice of i.

2. Let A be the adjacency matrix of a graph G with minus degree of vertices on the corresponding
diagonal entry (so that det ( A) = 0). Now let A−1 be the matrix one obtains by removing first
row and column of A. Prove that the number of spanning trees in G is the absolute value of the
determinant of A−1 . [hint: use a variant of incidence matrix of G to express A.]

Question 3.
A+ AT
Let A be an n × n matrix with real entries and let H = 2 . Assume that H is positive definite. Prove
that det H ≤ det A.

Question 4.
A linear operator A on a vector space V over field F is called an involution if A2 = I where I is the
identity operator on V. Assume further that characteristic of F is not equal to 2 and dimV = n < ∞.

1. Prove that for every involution A on V there exists a basis of V consisting of eigenvectors of A.

2. Find the maximal number of distinct pairwise commuting involutions on V.

Question 5.
Let A be an n × n matrix of real numbers for some n ≥ 1. For each positive integer k, let A[k] be the
matrix obtained by raising each entry to the kth power. Show that if Ak = A[k] for k = 1, 2, . . . , n + 1, then
Ak = A[k] for all k ≥ 1.

Question 6.
Say that a polynomial with real coefficients in two variables, x, y, is balanced if the average value of the
polynomial on each circle centered at the origin is 0. The balanced polynomials of degree at most 2009
form a vector space V over R. Find the dimension of V.

Question 7.
Let dn be the determinant of the n × n matrix whose entries, from left to right and then from top to
bottom, are cos 1, cos 2, . . . , cos n2 . (For example,

cos 1 cos 2 cos 3

d3 = cos 4 cos 5 cos 6 .
cos 7 cos 8 cos 9

The argument of cos is always in radians, not degrees.) Evaluate limn→∞ dn .

Question 8.
In the linear space of all n × n matrices, find the maximum possible dimension of a linear subspace V
such that
∀ X, Y ∈ V tr ( XY ) = 0
(The trace of a matrix is the sum of the diagonal entries.)

Question 9.
Let A be a n × n-matrix with integer entries and b1 , . . . , bk be integers satisfying det ( A) = b1 · · · · ·
bk . Prove that there exist n × n-matrices B1 , . . . , Bk with integer entries such that A = B1 · · · · · Bk and
det ( Bi ) = bi for all i = 1, . . . , k.

Question 10.
Let α ∈ R \ {0} and suppose F and G are linear maps (operators) from Rn into Rn satisfying F ◦ G − G ◦
F = αF.

• Show that for all k ∈ N one has F k ◦ G − G ◦ F k = αkF k .

• Show that there exists k ≥ 1 such that F k = 0.

Question 11.
Let M be invertible matrix of dimension 2n × 2n, represented in block form as
   
A B −1 E F
M= ,M =
C D G H

Show that det ( M ) det ( H ) = det ( A) .

Question 12.
For an m × m real matrix A, e A is defined as ∑∞ 1 n
n=0 n! A . (The sum is convergent for all matrices.) Prove,
that for all real polynomials p and m × m real matrices A and B, p(e AB ) is nilpotent if and only if p(e BA )
is nilpotent. (A matrix A is nilpotent if Ak = 0 for some positive integer k.)