Monthly Archives: November 2015

Some Interesting Linear Algebra Proofs

Below are some cute linear algebra results and proofs cherrypicked from various sources. All the standard hypotheses (on the base field, the size of the matrices, etc.) that make the claims valid are assumed. The list will likely be updated.

Fact 1. Let A,B,X be matrices. If AX=XB, then p(A)X=Xp(B) for any polynomial p.

Proof. We have A^2X=A(AX)=A(XB)=(AX)B=(XB)B=XB^2. By induction, A^nX=XB^n for any n\in\mathbb N. Hence the result follows. \square

Remark. Note that X need not be square, let alone invertible.

Fact 2. Let x_0,\dots,x_n be distinct. Then the Vandermonde matrix

\displaystyle V=\begin{pmatrix} 1 & x_0 & \cdots & x_0^n\\ 1 & x_1 & \cdots & x_1^n\\ \vdots & \vdots & \ddots & \vdots\\ 1 & x_n & \cdots & x_n^n\end{pmatrix}

is invertible.

Proof. It suffices to show that the kernel of the linear transformation f(x)=Vx is trivial. If a=(a_0,\dots,a_n) is in the kernel, then p(X)=a_0+a_1X+\cdots+a_nX^n=0 for each X\in\{x_0,\dots,x_n\}. Since \deg(p)=n, this forces p(X) to be identically zero. Thus a=0. \square

Fact 3. A matrix is diagonalisable iff its minimal polynomial decomposes into distinct linear factors.

Proof. A matrix is diagonalisable iff every Jordan block has size 1. Since the multiplicity of an eigenvalue in the minimal polynomial corresponds to the size of the largest Jordan block, the result follows. \square

Corollary. Idempotent matrices are diagonalisable. Moreover, the rank of an idempotent matrix is equal to the algebraic multiplicity of the eigenvalue 1.

Fact 4. If A^nx=0 and A^{n-1}x\neq 0, then x,Ax,\dots,A^{n-1}x are linearly independent.

Proof. Note that \ker(A^n)\supseteq\ker(A^{n-1}). Let x\in\ker(A^n)\setminus\ker(A^{n-1}) and suppose that a_0x+a_1Ax+\cdots+a_{n-1}A^{n-1}x=0. Multiplying both sides by A^i for i=n-1,\dots,1 shows that a_i=0 for all i, as desired. \square

Corollary 1. If \ker(A^n)\neq\ker(A^{n-1}), then \dim(\ker(A^j))\ge j for j=1,\dots,n.

Proof. If x\in\ker(A^n)\setminus\ker(A^{n-1}), then A^{n-1}x,\dots,A^{n-j}x\in\ker(A^j). \square

Corollary 2. If A is n\times n, and \ker(A^n)\neq\ker(A^{n-1}), then \dim(\ker(A^j))=j for each 0\le j\le n. In particular, A is similar to the nilpotent Jordan block of size n.

Fact 5. If f is linear on V, then V\cong\ker(f)\oplus f(V).

Proof. The short exact sequence

0\to\ker(f)\hookrightarrow V\twoheadrightarrow f(V)\to 0

is split. So the result follows by the splitting lemma. \square

Corollary. If W\subseteq V is a subspace, then V\cong W\oplus W^\perp.

Fact 6. If A is n\times n, then r(A)\ge n-k, where k is the algebraic multiplicity of the eigenvalue 0 of A.

Proof. Since the nullity of A is the geometric multiplicity of the eigenvalue 0, and the geometric multiplicity of an eigenvalue is at most its algebraic multiplicity, we get r(A)=n-n(A)\ge n-k. \square

Fact 7. The number of distinct eigenvalues of A is at most r(A)+1.

Proof. The rank of a matrix is the number of non-zero eigenvalues and the nullity is the number of zero eigenvalues, both counted with multiplicity. \square

Leave a comment

Filed under Linear Algebra

A Bound on the Multiplicative Order

Let n=p_1^{a_1}\cdots p_k^{a_k} factored uniquely into primes, and let a be an integer coprime to n. If we denote by \hbox{ord}_na the multiplicative order of a modulo n then Euler’s theorem tells us that \hbox{ord}_na\mid\phi(n), so that \hbox{ord}_na\le\phi(n). Can we do better?

Note that a^{p_i^{a_i-1}(p_i-1)}\equiv 1\pmod{p_i^{a_i}} for each i by Euler’s theorem. Hence

(*)\qquad\qquad\begin{aligned}\hbox{ord}_na&\le [p_1^{a_1-1}(p_1-1),\dots,p_k^{a_k-1}(p_k-1)]\\ &=\frac{\phi(n)}{(p_1^{a_1-1}(p_1-1),\dots,p_k^{a_k-1}(p_k-1))^{k-1}}\end{aligned}

using a result from this post. Now if 2\parallel n, then the GCD on the right-hand side is equal to 1. Otherwise 2 divides the GCD, so that


By the Chinese Remainder Theorem we can choose a to be a primitive root modulo p_i^{a_i} for i=1,\dots,k simultaneously. Hence equality can be achieved in (*) for any n. Further, if one of the p_i is 2 and one is congruent to 3\pmod 4 then the GCD in (*) is exactly 2, so that equality is achieved in (**). So (**) is the best uniform bound if n\not\equiv 2\pmod 4, while if n\equiv 2\pmod 4 then \hbox{ord}_na\le \phi(n) is uniformly the best possible.

Leave a comment

Filed under Number Theory

A Weaker Version of Burnside’s Theorem

Burnside’s theorem in group theory asserts that if p, q are prime numbers and a, b are non-negative integers then a group of order p^aq^b is soluble.

As outlined in the Wikipedia article, the proof of this theorem is not simple and most proofs make use of representation theory. Under a weaker hypothesis, however, we can give the following simpler proof using Sylow’s theorems.

Theorem. Let G be a finite group of order p^aq^b. Suppose that a<\hbox{ord}_qp or b<\hbox{ord}_pq. Then G is soluble.

Note that if p=q then the hypothesis is trivially satisfied.

An immediate corollary is the following.

Corollary. Every group of order pq is soluble.

To prove the Theorem we shall make use of the following two lemmas.

Lemma 1. If H is a normal subgroup of G then G is soluble iff both H and G/H are soluble.

Proof. See here\square

Lemma 2. Finite p-groups are soluble.

Proof. We prove by induction on n\ge 0 that a group G of order p^n is soluble. The result is trivial for n=0 so assume that n\ge 1. Using the class equation one easily deduces that the centre Z of G is non-trivial. Hence Z is a normal subgroup of G. If Z=G then G is abelian and the result is clear. Otherwise Z is a proper normal subgroup of G, so that by the induction hypothesis both Z and G/Z are soluble. Thus G is soluble by Lemma 1. \square

Proof of the Theorem. If p=q we are done by Lemma 2, so assume that p\neq q. Without loss of generality assume that b<\hbox{ord}_pq. Let n_p denote the number of Sylow p-subgroups of G. By the Sylow theorems, n_p\mid q^b and n_p\equiv 1\pmod p, i.e., n_p=q^j\equiv 1\pmod p, for some 0\le j\le b. But b<\hbox{ord}_pq, which forces j=0, i.e., n_p=1. Let H be the unique Sylow p-subgroup of G. Then by the second Sylow theorem H must be self-conjugate, i.e., a normal subgroup of G.

By Lemma 2 both H (which has order p^a) and G/H (which has order q^b) are soluble. Thus G is soluble, as desired. \square

Leave a comment

Filed under Algebra