Search for probability and statistics terms on Statlect
StatLect
Index > Matrix algebra

Primary decomposition theorem

by , PhD

The primary decomposition theorem allows us to use the minimal polynomial of a matrix to write a vector space as a direct sum of invariant subspaces. It is key to understanding and interpreting the information provided by the minimal polynomial.

Table of Contents

Preview of the theorem

Let $S$ be the space of Kx1 vectors. Let A be a $K	imes K$ matrix.

Remember that a subspace $Usubseteq S$ is said to be invariant under the linear transformation defined by A if and only if [eq1]for any $uin U$. In other words, $U$ is invariant if its elements are transformed by A into other elements of $U$.

The minimal polynomial of A is the monic annihilating polynomial (i.e., [eq2] and the leading coefficient of p is 1) that divides every annihilating polynomial of A.

The minimal polynomial is the lowest-degree polynomial in the set of annihilating polynomials and it has the property that[eq3]where [eq4] are the distinct eigenvalues of A and [eq5] for any $j=1,ldots ,m$, where $mu _{j}$ is the algebraic multiplicity of $lambda _{j}$.

We can write the minimal polynomial in terms of A as[eq6]where I is the $K	imes K$ identity matrix.

In this lecture we are going to prove the Primary Decomposition Theorem, which states that the vector space $S$ can be written as[eq7]where [eq8] denotes the null space of the matrix [eq9], that is,[eq10]and $oplus $ denotes a direct sum.

Thus, by the definition of direct sum, we will be able to uniquely write each vector $sin S$ as[eq11]where $u_{j}in $ [eq12] for $j=1,ldots ,m$. Moreover, the vectors [eq13] are guaranteed to be linearly independent whenever they are non-zero.

Furthermore, we will show that the null spaces [eq14] are invariant.

A first decomposition

The next proposition paves the way to the Primary Decomposition Theorem.

Proposition Let $S$ be the space of Kx1 vectors. Let A be a $K	imes K$ matrix. Let $f_{1}$ and $f_{2}$ be two polynomials such that: 1) they are relatively prime (i.e., their greatest common divisor is 1); 2) they are not identically equal to zero; 3) [eq15] is an annihilating polynomial. Then,[eq16]and [eq17] and [eq18] are invariant under the linear transformation defined by A.

Proof

Since $f_{1}$ and $f_{2}$ are relatively prime and not identically equal to zero, by Bezout's theorem there exists two polynomials $p_{1}$ and $p_{2}$ such that[eq19]Thus,[eq20]Arbitrarily choose any $sin S$ and post-multiply both sides of the previous equation by $s$:[eq21]where we have defined[eq22]The previous two equations can be pre-multiplied by [eq23] and [eq24] so as to obtain [eq25]which imply that [eq26]Since $s$ was arbitrary, we have[eq27]that is, any $sin S$ can be written as the sum of an element of [eq28] and an element of [eq29]. In order to show that the sum is direct, we are going to prove that the representation[eq30]is unique. Suppose there is another representation[eq31]where [eq32] and [eq33]. Subtracting equation (2) from equation (3), we obtain[eq34]Post-multiplying equation (1) by $t_{1}-s_{1}$, we get [eq35]where: in step $rame{A}$ we have used the fact that $t_{1}$ and $s_{1}$ belong to [eq36]; in step $rame{B}$ we have used equation (4); in step $rame{C}$ we have used the fact that $t_{2}$ and $s_{2}$ belong to [eq37]. Thus, $t_{1}=s_{1}$. In a completely analogous manner, we can prove that $t_{2}=s_{2}$. As a consequence, the representation as a sum is unique, which implies that[eq38]Moreover, by the properties of matrix polynomials, the null spaces [eq17] and [eq40] are invariant under the linear transformation defined by A.

A simple example follows.

Example Consider the space $S$ of all $3	imes 1$ vectors and a $3	imes 3$ matrix $A $ whose characteristic polynomial is[eq41]In other words, A has an eigenvalue $lambda _{1}=1$ with algebraic multiplicity 1 and another eigenvalue $lambda _{2}=2$ with algebraic multiplicity $2$. The two polynomials[eq42]satisfy all the assumptions of the previous proposition because, by the Cayley-Hamilton theorem, the characteristic polynomial is an annihilating polynomial. Then,[eq43]where the two spaces [eq44] and [eq45] are invariant.

The theorem

Here is the Primary Decomposition Theorem.

Proposition Let $S$ be the space of Kx1 vectors. Let A be a $K	imes K$ matrix. Let p be the minimal polynomial of A: [eq46]where [eq4] are the distinct eigenvalues of A. Then,[eq48]where the spaces [eq49], ..., [eq50] are invariant under the linear transformation defined by A.

Proof

This proposition is proved by applying recursively the previous proposition. We start with the two polynomials [eq51]They are relatively prime, non-zero, and their product is an annihilating polynomial since it is equal to the minimal polynomial. Therefore,[eq52]We now restrict our attention to the space [eq53]. We define the two polynomials[eq54]They are relatively prime, non-zero, and their product $f_{2}g_{2}=g_{1}$ is, by definition, an annihilating polynomial on the space [eq55]. Therefore,[eq56]and[eq57]We then decompose, with the same technique, the spaces [eq58], ..., [eq59] until we obtain[eq60]

Thus, the space $S$ can be written as a direct sum of invariant spaces of the form[eq61]which contain vectors $s$ such that[eq62]These vectors are called generalized eigenvectors and the spaces [eq63] are called generalized eigenspaces.

In the special case in which $v_{j}=1$, then[eq64]that is, $s$ is an eigenvector of A associated to the eigenvalue $lambda _{j}$ and [eq65] is the eigenspace of $lambda _{j}$.

The key to interpreting the minimal polynomial

The Primary Decomposition Theorem provides the key to understanding the information provided by the minimal polynomial.

It is natural to make a comparison with the characteristic polynomial[eq66]which reveals the eigenvalues [eq4] and their algebraic multiplicities [eq68], but contains no information on the eigenspaces.

The minimal polynomial[eq69]also reveals the eigenvalues, but not their algebraic multiplicities; however, it provides an additional piece of information: by looking at the exponents [eq70], we can understand whether the eigenspaces are "large enough" to contain a basis of eigenvectors for the space $S$. As explained above and in the next section, if [eq71], then the space $S$ can be written as a direct sum of eigenspaces, which implies that the eigenvectors of A are sufficient to form a basis for $S$. On the contrary, if an exponent $v_{j}$ is greater than 1, then the eigenspace associated to $lambda _{j}$ is not "large enough" and we are not able to find a basis of eigenvectors for $S$ (the eigenvalue $lambda _{j}$ is defective). The remedy is to resort to "larger" generalized eigenspaces. What do we mean by larger? In the lecture on matrix powers, we have learned that the larger the power of a matrix is, the larger its null space is. Therefore, if an eigenspace[eq72]does not contain enough linearly independent vectors (to be used in the construction of a basis for $S$), then we look at larger powers ($v_{j}>1$) of the matrix $A-lambda _{j}I$, so as to obtain larger null spaces [eq73]called generalized eigenspaces.

Thus, the minimal polynomial reveals by how much we need to enlarge the (generalized) eigenspaces in order to be able to form a basis for the space $S$.

Example Let A be a $4	imes 4$ matrix. Suppose that the characteristic polynomial of A is[eq74]and the minimal polynomial of A is[eq75]The eigenvalue $lambda _{1}=3$ has algebraic multiplicity equal to $2$ (inferred from the characteristic polynomial), it is not defective (inferred from the exponent equal to 1 in the minimal polynomial) and, as a consequence, its geometric multiplicity is equal to $2$. The eigenvalue $lambda _{2}=4$ has algebraic multiplicity equal to $2$ (inferred from the characteristic polynomial), it is defective (inferred from the exponent equal to $2$ in the minimal polynomial) and, as a consequence, its geometric multiplicity must be less than $2$ (hence 1).

Diagonalizable matrices and minimal polynomials

Remember that a matrix is diagonalizable if and only if

  1. it is similar to a diagonal matrix;

  2. its eigenvalues are not defective (their algebraic and geometric multiplicities coincide);

  3. there exists a basis of eigenvectors for $S$.

Thanks to the Primary Decomposition Theorem, we can provide another criterion for the diagonalizability of a matrix.

Proposition Let A be a $K	imes K$ matrix. Let p be the minimal polynomial of A: [eq69]where [eq4] are the distinct eigenvalues of A. Then, A is diagonalizable if and only if [eq78]

Proof

Let us prove the "if" part, starting from the assumption that $v_{j}=1$ for every $j$. Let $S$ be the space of Kx1 vectors. Then,[eq79]In other words, $S$ is the direct sum of the eigenspaces of A. Pick any vector $sin S$. Then, we can write[eq80]where $s_{j}$ belongs to the eigenspace [eq81] for each $j$. We can choose a basis $B_{j}$ for each eigenspace [eq82] and form the union[eq83]which is a set of linearly independent vectors and a basis for $S$ because $S$ is a direct sum. The vector $s$ can be re-written in terms of the basis $B$ by writing each $s_{j}$ in terms of the basis $B_{j}$. Since this is true for an arbitrary vector $sin S$, we have that $B$ is a basis of eigenvectors of A for the space $S$. Hence, A is diagonalizable. Let us now prove the "only if" part, starting from the assumption that A is diagonalizable. As proved in the lecture on the minimal polynomial, $
u _{j}>0$ for every $j$ (otherwise p is not an annihilating polynomial). We are going to prove that, when A is diagonalizable, p becomes an annihilating polynomial by setting [eq84] (hence it is the minimal polynomial because any other annihilating polynomial has higher degree). Since A is similar to a diagonal matrix $D$ (having the eigenvalues [eq4] on its main diagonal), we need to check whether [eq86] is an annihilating polynomial of $D$ (two similar matrices have the same annihilating polynomials). But[eq87]because all the diagonal elements of $D$ are products involving factors of the form [eq88], at least one of which is such that $j=k$. This proves that p is the minimal polynomial of A and has the desired property ([eq89]).

Solved exercises

Below you can find some exercises with explained solutions.

Exercise 1

Let A be a $3	imes 3$ matrix. Suppose that the minimal polynomial of A is[eq90]

Is A diagonalizable?

Solution

The matrix A is not diagonalizable because the exponent of the linear factor $left( z-2
ight) $ is greater than 1.

Exercise 2

Let A be a $3	imes 3$ matrix. Suppose that the characteristic polynomial of A is[eq91]and the minimal polynomial of A is[eq92]What is the geometric multiplicity of the eigenvalue $lambda _{1}=-1$?

Solution

From the characteristic polynomial, we infer that the algebraic multiplicity of $lambda _{1}$ is $2$. From the minimal polynomial, we infer that it is not defective. Hence, its geometric multiplicity equals $2$.

Exercise 3

Let $S$ be the space of Kx1 vectors. Let A be a $K	imes K$ matrix. Let $c$ be the characteristic polynomial of A: [eq93]where [eq4] are the distinct eigenvalues of A and [eq68] are their respective algebraic multiplicities. Can you modify the Primary Decomposition Theorem so as to write $S$ as a sum of null spaces by using the characteristic polynomial instead of the minimal polynomial?

Solution

The recursive decomposition used in the proof of the Primary Decomposition Theorem does not depend on any specific property possessed by the minimal polynomial and not by the characteristic one. For example, we can start the decomposition with [eq96]They are relatively prime, non-zero, and their product is an annihilating polynomial since it is equal to the characteristic polynomial. Therefore,[eq97]We can then decompose [eq98] and keep decomposing the null spaces until we obtain[eq99]

How to cite

Please cite as:

Taboga, Marco (2017). "Primary decomposition theorem", Lectures on matrix algebra. https://www.statlect.com/matrix-algebra/primary-decomposition-theorem.

The book

Most of the learning materials found on this website are now available in a traditional textbook format.