Primary Decomposition Theorem

From ProofWiki
Jump to navigation Jump to search


Theorem

Let $K$ be a field.

Let $V$ be a vector space over $K$.

Let $T: V \to V$ be a linear operator on $V$.

Let $\map p x \in K \sqbrk x$ be a polynomial such that:

$\map \deg p \ge 1$
$\map p T = 0$

where $0$ is the zero operator on $V$.



Let $\map {p_1} x, \map {p_2} x, \ldots, \map {p_r} x$ be distinct irreducible monic polynomials.

Let $c \in K \setminus \set 0$ and $a_1, a_2, \ldots, a_r, r \in \Z_{\ge 1}$ be constants.

We have that:

$\map p x = c \map {p_1} x^{a_1} \map {p_2} x^{a_2} \dotsm \map {p_r} x^{a_r}$


The primary decomposition theorem then states the following :

$(1): \quad \map \ker {\map {p_i} T^{a_i} }$ is a $T$-invariant subspace of $V$ for all $i = 1, 2, \dotsc, r$
$(2): \quad \displaystyle V = \bigoplus_{i \mathop = 1}^r \map \ker {\map {p_i} T^{a_i} }$




Proof of $(1)$

Let $v \in \map \ker {\map {p_i} T^{a_i} }$.


Then:

\(\displaystyle \map {\map {p_i} T^{a_i} } {\map T v}\) \(=\) \(\displaystyle \map T {\map {\map {p_i} T^{a_i} } v}\) because $\map {p_i} T^{a_i} \circ T = T \circ \map {p_i} T^{a_i}$
\(\displaystyle \) \(=\) \(\displaystyle \map T 0\) because $v \in \map \ker {\map {p_i} T^{a_i} } \iff \map {\map {p_i} T^{a_i} } v = 0$
\(\displaystyle \) \(=\) \(\displaystyle 0\) where $0$ is the zero vector in $V$ (if $T$ is any linear transformation, then $\map T 0 = 0$)

This shows that:

$\map T v \in \map \ker {\map {p_i} T^{a_i} }$

for all $v \in \map \ker {\map {p_i} T^{a_i} }$.

This is because $v$ was first arbitrary in $\map \ker {\map {p_i} T^{a_i} }$.

That is:

$\map \ker {\map {p_i} T^{a_i} }$

is a $T$-invariant subspace of $V$.

$\blacksquare$


Proof of $(2)$

Proof by induction on $r$:

For all $r \in \Z_{\ge 1}$, let $P(r)$ be the proposition:

$V = \displaystyle \bigoplus_{i \mathop = 1}^r \map \ker {\map {p_i} T^{a_i} }$

where $\map {p_i} x^{a_i}$ for $i = 1, 2, \dotsc, r$ satisfy the hypotheses of the theorem.

$V$ and $T$ are arbitrary.


Basis for the Induction

We have:

\(\displaystyle \map p T\) \(=\) \(\displaystyle c \map {p_1} T^{a_1}\)
\(\displaystyle \) \(=\) \(\displaystyle 0\)
\(\displaystyle \leadsto \ \ \) \(\displaystyle \map {p_1} T^{a_1}\) \(=\) \(\displaystyle 0\)
\(\displaystyle \leadsto \ \ \) \(\displaystyle V\) \(=\) \(\displaystyle \map \ker {\map {p_1} T^{a_1} }\)

Thus $\map P 1$ holds.

This is our basis for the induction


Induction Hypothesis

Now we need to show that, if $\map P k$ is true, where $k \ge 2$, then it logically follows that $\map P {k + 1}$ is true.

So this is our induction hypothesis:

$V = \displaystyle \bigoplus_{i \mathop = 1}^{k - 1} \map \ker {\map {p_i} T^{a_i} }$

where $\map {p_i} x^{a_i}$ for $i = 1, 2, \dotsc, r$ satisfy the hypotheses of the theorem.

$V$ and $T$ are arbitrary.


Then we need to show:

$V = \displaystyle \bigoplus_{i \mathop = 1}^k \map \ker {\map {p_i} T^{a_i} }$


Induction Step

Suppose we meet the hypotheses of the theorem when $r = k$.

Then:

$\map p x \in K \sqbrk x$

is a polynomial such that:

$\map \deg p \ge 1$
$\map p T = 0$
$\map p x = c \map {p_1} x^{a_1} \map {p_2} x^{a_2} \cdots \map {p_k} x^{a_k}$

Let $W := \map \ker {\map {p_2} T^{a_2} \cdots \map {p_k} T^{a_k} }$.

First it will be shown that $W$ is a $T$-invariant subspace of $V$.

Let $w \in W$.

Then:

\(\displaystyle \map {\map {p_2} T^{a_2} \cdots \map {p_k} T^{a_k} } {\map T w}\) \(=\) \(\displaystyle \map T {\map {\map {p_2} T^{a_2} \cdots \map {p_k} T^{a_k} } w}\) by the same argument as in the proof of i), first equality
\(\displaystyle \) \(=\) \(\displaystyle \map T 0\) because $w \in W \iff \map {\map {p_2} T^{a_2} \cdots \map {p_k} T^{a_k} } w = 0$
\(\displaystyle \) \(=\) \(\displaystyle 0\) where $0$ is the zero vector in $V$ (if $T$ is any linear transformation, then $\map T 0 = 0$)

This shows that $\map T w \in W$ for all $w \in W$, because $w$ was first arbitrary in $W$.

That is, $W$ is a $T$-invariant subspace of $V$.

So it makes sense to talk about the restriction $T \restriction_W$ of $T$ on $W$.


Now, define:

$\map q x := \map {p_2} x^{a_2} \cdots \map {p_k} x^{a_k}$

Let $w \in W$.

Then:

\(\displaystyle \map {\map q {T \restriction_W} } w\) \(=\) \(\displaystyle \map {\map {p_2} {T \restriction_W}^{a_2} \cdots \map {p_k} {T \restriction_W}^{a_k} } w\)
\(\displaystyle \) \(=\) \(\displaystyle \map {\map {p_2} T^{a_2} \cdots \map {p_k} T^{a_k} } w\) because $\map {T \restriction_W} w = \map T w$ for all $w \in W$
\(\displaystyle \) \(=\) \(\displaystyle 0\) because $w \in W \iff \map {p_2} T^{a_2} \cdots \map {\map {p_k} T^{a_k} } w = 0$

Because $w$ was arbitrary in $W$, this shows that $\map q {T \restriction_W} = 0$, where $0$ is the zero operator on $W$.

The hypotheses of the theorem are met.

So, by the induction hypothesis:

$\displaystyle W = \bigoplus_{i \mathop = 2}^k \map \ker {\map {p_i} {T \restriction_W}^{a_i} }$


Now we show that:

$\map \ker {\map {p_i} {T \restriction_W}^{a_i} } = \map \ker {\map {p_i} T^{a_i} }$

for all $i = 2, \dotsc, k$.


Thus, for all $i = 2, \dotsc, k$:

\(\displaystyle \map \ker {\map {p_i} {T \restriction_W}^{a_i} }\) \(=\) \(\displaystyle \set {w \in W: \map {\map {p_i} {T \restriction_W}^{a_i} } w = 0}\)
\(\displaystyle \) \(=\) \(\displaystyle \set {w \in W: \map {\map {p_i} T^{a_i} } w = 0}\)
\(\displaystyle \) \(\subseteq\) \(\displaystyle \map \ker {\map {p_i} T^{a_i} }\)
\(\displaystyle \) \(=\) \(\displaystyle \set {v \in V: \map {\map {p_i} T^{a_i} } v = 0}\)


Then:

$\map \ker {\map {p_i} T^{a_i} } \subseteq W$

for all $i = 2, \dotsc, k$.

Let:

$v \in \map \ker {\map {p_j} T^{a_j} }$

where $j \in \set {2, \dotsc, k}$.

Then:

\(\displaystyle \map {\map {p_2} T^{a_2} \cdots \map {p_j} T^{a_j} \cdots \map {p_k} T^{a_k} } v\) \(=\) \(\displaystyle \map {\map {p_2} T^{a_2} \cdots \map {p_k} T^{a_k} } {\map {\map {p_j} T^{a_j} } v}\) by the same argument than in the proof of i), first equality
\(\displaystyle \) \(=\) \(\displaystyle \map {\map {p_2} T^{a_2} \cdots \map {p_k} T^{a_k} } 0\) because $v \in \map \ker {\map {p_j} T^{a_j} } \iff \map {\map {p_j} T^{a_j} } v = 0$
\(\displaystyle \) \(=\) \(\displaystyle 0\) where $0$ is the zero vector in $V$ (if $T$ is any linear transformation, then $\map T 0 = 0$)


So:

$v \in \map \ker {\map {p_2} T^{a_2} \cdots \map {p_k} T^{a_k} } = W$

and:

$\map \ker {\map {p_j} T^{a_j} } \subseteq W$

because $v$ was arbitrary in $\map \ker {\map {p_j} T^{a_j} }$.

So:

$v \in \map \ker {\map {p_i} T^{a_i} } \implies v \in W$

and so:

$\map {\map {p_i} {T \restriction_W}^{a_i} } v = \map {\map {p_i} T^{a_i} } v = 0$

for all $i = 2, \dotsc, k$.


Finally, because $v$ was arbitrary in $\map \ker {\map {p_i} T^{a_i} }$:

$v \in \map \ker {\map {p_i} {T \restriction_W}^{a_i} }$

and:

$\map \ker {\map {p_i} T^{a_i} } \subseteq \map \ker {\map {p_i} {T \restriction_W}^{a_i} }$

for all $i = 2, \dotsc, k$.

This shows that:

$\map \ker {\map {p_i} {T \restriction_W}^{a_i} } = \map \ker {\map {p_i} T^{a_i} }$

for all $i = 2, \dotsc, k$.

So we conclude that:

$\displaystyle W = \bigoplus_{i \mathop = 2}^k \map \ker {\map {p_i} T^{a_i} }$


In order to show that:

$V = \displaystyle \bigoplus_{i \mathop = 1}^k \map \ker {\map {p_i} T^{a_i} }$

we equivalently show that:

$(a): \quad V = W + \map \ker {\map {p_1} T^{a_1} }$
$(b): \quad W \cap \map \ker {\map {p_1} T^{a_1} } = 0$

where $0 = \set 0 \subseteq V$.


Notice that $(b)$ is equivalent to showing that:

$\map \ker {\map {p_1} T^{a_1} } \cap \map \ker {\map {p_i} T^{a_i} } = 0$

for all $i = 2, \dotsc, k$.

In particular, $(b)$ implies this last result, because $\map \ker {\map {p_i} T^{a_i} } \subseteq W$ for all $i = 2, \dotsc, k$.


$(a): \quad$ We have that:

$\map g x := \gcd \set {\map {p_1} x^{a_1}, \map {p_2} x^{a_2} \cdots \map {p_k} x^{a_k} } = 1 \in K$.

Indeed, $\map {p_1} x$ being an irreducible monic polynomial, either $\map g x = 1$ or $\map g x = \map {p_1} x^z$ for some $1 \le z \le a_1$.

But we know that the greatest common divisor of two polynomials divides both of these polynomials.

So we must conclude that $\map g x = 1$ because otherwise we would have $\map {p_1} x = \map {p_i} x$ for some $i \in \set {2, \ldots, k}$.

This is a contradiction with the hypothesis that the $\map {p_i} x$ ($i = 1, 2, \ldots, k$) are all distinct.

So, by Bézout's_Identity for polynomials, we know that:

$\exists \map h x, \map {h_1} x \in K \sqbrk x$

such that:

$1 = \map {h_1} x \map {p_1} x^{a_1} + \map h x \map {p_2} x^{a_2} \cdots \map {p_k} x^{a_k}$

Let $v \in V$.

Then, evaluating the last polynomial equality at $T$, and evaluating the resulting operator at $v$, we obtain:

$v = \map {\map {h_1} T \map {p_1} T^{a_1} } v + \map {\map h T \map {p_2} T^{a_2} \cdots \map {p_k} T^{a_k} } v$

Notice that $\map I v = v$ on the left hand side.

But:

\(\displaystyle \map {\map {p_1} T^{a_1} } {\map {\map h T \map {p_2} T^{a_2} \cdots \map {p_k} T^{a_k} } v}\) \(=\) \(\displaystyle \map {\map h T} {\map {\map {p_1} T^{a_1} \map {p_2} T^{a_2} \cdots \map {p_k} T^{a_k} } v}\) by the same argument as in the proof of $(1)$, first equality
\(\displaystyle \) \(=\) \(\displaystyle \map h t \paren {\frac 1 c \map {\map p T} v}\)
\(\displaystyle \) \(=\) \(\displaystyle 0\) because $\map p T$ is the zero operator on $V$ by hypothesis

So:

$\map h T \map {p_2} T^{a_2} \cdots \map {p_k} T^{a_k} \in \map \ker {\map {p_1} T^{a_1} }$

Similarly, we find that:

$\map {\map {p_2} T^{a_2} \map {p_3} T^{a_3} \cdots \map {p_k} T^{a_k} } {\map {\map {h_1} T \map {p_1} T^{a_1} } v} = 0$

and so:

$\map {\map {h_1} T \map {p_1} T^{a_1} } v \in \map \ker {\map {p_2} T^{a_2} \map {p_3} T^{a_3} \cdots \map {p_k} T^{a_k} } = W$

Because $v$ was arbitrary in $V$:

$v = \map {h_1} T \map {p_1} T^{a_1} v + \map h T \map {p_2} T^{a_2} \cdots \map {p_k} T^{a_k} v \implies V = W + \map \ker {\map {p_1} T^{a_1} }$


$(b): \quad$ Define:

$S := W \cap \map \ker {\map {p_1} T^{a_1} }$
$M := \set {\map f x \in K \sqbrk x: \map {\map f T} s = 0 \forall s \in S}$

and:

$\map q x := \map \gcd M$

By definition of $W$:

$\map {p_2} x^{a_2} \cdots \map {p_k} x^{a_k} \in M$

As every element of $S$ is also an element of $\map \ker {\map {p_1} T^{a_1} }$:

$\map {p_1} x^{a_1} \in M$

it follows that:

$\map q x \divides \map {p_1} x^{a_1}$

and:

$\map q x \divides \map {p_2} x^{a_2} \dotsm \map {p_k} x^{a_k}$

We know that the greatest common divisor $\map {u_1} x$ of two polynomials $\map {u_2} x$ and $\map {u_3} x$ has the property that:

if a polynomial $\map {u_4} x$ divides both $\map {u_2} x$ and $\map {u_3} x$
then $\map {u_4} x$ must also divide $\map {u_1} x$.

Thus, we must have:

$\map q x \divides \gcd \set {\map {p_1} x^{a_1}, \map {p_2} x^{a_2} \cdots \map {p_k} x^{a_k} } = \map g x = 1$

So:

$\map q x = \map g x = 1$

Bézout's_Identity for polynomials may then be applied to obtain:

$\map q x = 1 = \map {h_1} x \map {p_1} x^{a_1} + \map {h_2} x \map {p_2} x^{a_2} \dotsm \map {p_k} x^{a_k}$

for some $\map {h_1} x, \map {h_2} x \in K \sqbrk x$.

Let $s \in S$.

Then, evaluating the last polynomial equality at $T$, and evaluating the resulting operator at $s$, we obtain, by definition of $M$ and by noticing that the left hand side then becomes $\map I s = s$:

$s = \map {\map {h_1} T \map {p_1} T^{a_1} } s + \map {\map {h_2} T \map {p_2} T^{a_2} \cdots \map {p_k} T^{a_k} } s = 0$

Because $s$ was arbitrary in $S$, it follows that:

$S = W \cap \map \ker {\map {p_1} T^{a_1} } = 0$

$\blacksquare$

Remarks


$V$ need not be of finite dimension, but if it is then we can see $T$ as its matrix in the equations and the notation $T^j$ is then directly related to matrix multiplication.

By definition, when applying $\map p x$ at $T$, one needs to convert constants which may appear in the expression of $\map p x$ into transformations in the following way

For example, if $\map p x = 2 + x$, then $\map p T = 2 I + T$, where $I$ is the identity application $I: V \to V$.

$\map {p_1} x, \map {p_2} x, \dotsc, \map {p_r} x$ are not necessarily of degree $1$.

For example, if $K = \R$ and $\map p x = x^2 + 1$, then $\map p x$ is irreducible on $\R$ and $\map {p_1} x = \map p x$ is of degree $2$.

$T^j \triangleq \begin{cases} \overbrace {T \circ T \circ \cdots \circ T}^{\text {$j$ times} } & : j \in \Z_{\ge 1} \\ I: V \to V & : j = 0 \end{cases}$



By definition, the greatest common divisor of two polynomials is a monic polynomial.