Primary Decomposition Theorem

From ProofWiki
Jump to: navigation, 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 $p \left({x}\right) \in K \left[{x}\right]$ be a polynomial such that:

$\deg \left({p}\right) \ge 1$
$p \left({T}\right) = 0$

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



Let $p_1 \left({x}\right), p_2 \left({x}\right), \ldots, p_r \left({x}\right)$ be distinct irreducible monic polynomials.

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

We have that:

$p \left({x}\right) = c p_1 \left({x}\right)^{a_1} p_2 \left({x}\right)^{a_2} \dotsm p_r \left({x}\right)^{a_r}$


The primary decomposition theorem then states the following :

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




Proof of i)

Let $v \in \ker \left({p_i \left({T}\right)^{a_i} }\right)$.


Then:

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

This shows that:

$T \left({v}\right) \in \ker \left({p_i \left({T}\right)^{a_i} }\right)$

for all $v \in \ker \left({p_i \left({T}\right)^{a_i} }\right)$.

This is because $v$ was first arbitrary in $\ker \left({p_i \left({T}\right)^{a_i} }\right)$.

That is:

$\ker \left({p_i \left({T}\right)^{a_i} }\right)$

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

$\blacksquare$


Proof of ii)

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 \ker \left({p_i \left({T}\right)^{a_i} }\right)$

where $p_i \left({x}\right)^{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 p \left({T}\right)\) \(=\) \(\displaystyle c p_1 \left({T}\right)^{a_1}\) $\quad$ $\quad$
\(\displaystyle \) \(=\) \(\displaystyle 0\) $\quad$ $\quad$
\(\displaystyle \implies \ \ \) \(\displaystyle p_1 \left({T}\right)^{a_1}\) \(=\) \(\displaystyle 0\) $\quad$ $\quad$
\(\displaystyle \implies \ \ \) \(\displaystyle V\) \(=\) \(\displaystyle \ker \left({p_1 \left({T}\right)^{a_1} }\right)\) $\quad$ $\quad$

Thus $P(1)$ holds.

This is our basis for the induction


Induction Hypothesis

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

So this is our induction hypothesis :

$V = \displaystyle \bigoplus_{i \mathop = 1}^{k - 1} \ker \left({p_i \left({T}\right)^{a_i} }\right)$

where $p_i \left({x}\right)^{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 \ker \left({p_i \left({T}\right)^{a_i} }\right)$


Induction Step

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

Then:

$p \left({x}\right) \in K \left[{x}\right]$

is a polynomial such that:

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

Let $W := \ker \left({p_2 \left({T}\right)^{a_2} \cdots p_k \left({T}\right)^{a_k} }\right)$.

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

Let $w \in W$.

Then:

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

This shows that $T \left({w}\right) \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:

$q \left({x}\right) := p_2 \left({x}\right)^{a_2} \cdots p_k \left({x}\right)^{a_k}$

Let $w \in W$.

Then:

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

Because $w$ was arbitrary in $W$, this shows that $q \left({T \restriction_W}\right) = 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 \ker \left({p_i \left({T \restriction_W}\right)^{a_i} }\right)$


Now we show that:

$\ker \left({p_i \left({T \restriction_W}\right)^{a_i} }\right) = \ker \left({p_i \left({T}\right)^{a_i} }\right)$

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


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

\(\displaystyle \ker \left({p_i \left({T \restriction_W}\right)^{a_i} }\right)\) \(=\) \(\displaystyle \left\{ {w \in W: p_i \left({T \restriction_W}\right)^{a_i} \left({w}\right) = 0}\right\}\) $\quad$ $\quad$
\(\displaystyle \) \(=\) \(\displaystyle \left\{ {w \in W: p_i \left({T}\right)^{a_i} \left({w}\right) = 0}\right\}\) $\quad$ $\quad$
\(\displaystyle \) \(\subseteq\) \(\displaystyle \ker \left({p_i \left({T}\right)^{a_i} }\right)\) $\quad$ $\quad$
\(\displaystyle \) \(=\) \(\displaystyle \left\{ {v \in V: p_i \left({T}\right)^{a_i} \left({v}\right) = 0}\right\}\) $\quad$ $\quad$


Then:

$\ker \left({p_i \left({T}\right)^{a_i} }\right) \subseteq W$

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

Let:

$v \in \ker \left({p_j \left({T}\right)^{a_j} }\right)$

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

Then:

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


So:

$v \in \ker \left({p_2 \left({T}\right)^{a_2} \cdots p_k \left({T}\right)^{a_k} }\right) = W$

and:

$\ker \left({p_j \left({T}\right)^{a_j} }\right) \subseteq W$

because $v$ was arbitrary in $\ker(p_j \left({T}\right)^{a_j})$.

So:

$v \in \ker \left({p_i \left({T}\right)^{a_i} }\right) \implies v \in W$

and so:

$p_i \left({T \restriction_W}\right)^{a_i} \left({v}\right) = p_i \left({T}\right)^{a_i} \left({v}\right) = 0$

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


Finally, because $v$ was arbitrary in $\ker \left({p_i \left({T}\right)^{a_i} }\right)$:

$v \in \ker \left({p_i \left({T \restriction_W}\right)^{a_i} }\right)$

and:

$\ker \left({p_i \left({T}\right)^{a_i} }\right) \subseteq \ker \left({p_i \left({T \restriction_W}\right)^{a_i} }\right)$

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

This shows that:

$\ker \left({p_i \left({T \restriction_W}\right)^{a_i} }\right) = \ker \left({p_i \left({T}\right)^{a_i} }\right)$

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

So we conclude that:

$\displaystyle W = \bigoplus_{i \mathop = 2}^k \ker \left({p_i \left({T}\right)^{a_i} }\right)$


In order to show that:

$V = \displaystyle \bigoplus_{i \mathop = 1}^k \ker \left({p_i \left({T}\right)^{a_i} }\right)$

we equivalently show that:

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

where $0 = \left\{ {0}\right\}\subseteq V$.


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

$\ker \left({p_1 \left({T}\right)^{a_1} }\right) \cap \ker \left({p_i \left({T}\right)^{a_i} }\right) = 0$

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

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


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

$g \left({x}\right) := gcd \left\{ {p_1 \left({x}\right)^{a_1}, p_2 \left({x}\right)^{a_2} \cdots p_k \left({x}\right)^{a_k} }\right\} = 1 \in K$.

Indeed, $p_1 \left({x}\right)$ being an irreducible monic polynomial, either $g \left({x}\right) = 1$ or $g \left({x}\right) = p_1 \left({x}\right)^{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 $g \left({x}\right) = 1$ because otherwise we would have $p_1 \left({x}\right) = p_i \left({x}\right)$ for some $i \in \{ 2,\ldots,k \}$.

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

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

$\exists h \left({x}\right), h_1 \left({x}\right) \in K \left[{x}\right]$

such that:

$1 = h_1 \left({x}\right) p_1 \left({x}\right)^{a_1} + h \left({x}\right) p_2 \left({x}\right)^{a_2} \cdots p_k \left({x}\right)^{a_k}$

Let $v \in V$.

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

$v = h_1 \left({T}\right) p_1 \left({T}\right)^{a_1} \left({v}\right) + h \left({T}\right) p_2 \left({T}\right)^{a_2} \cdots p_k \left({T}\right)^{a_k} \left({v}\right)$

Notice that $I \left({v}\right) = v$ on the left hand side.

But:

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

So:

$h \left({T}\right) p_2 \left({T}\right)^{a_2} \cdots p_k \left({T}\right)^{a_k} \in \ker \left({p_1 \left({T}\right)^{a_1} }\right)$

Similarly, we find that:

$p_2 \left({T}\right)^{a_2} p_3 \left({T}\right)^{a_3} \cdots p_k \left({T}\right)^{a_k} \left({h_1 \left({T}\right) p_1 \left({T}\right)^{a_1} \left({v}\right) }\right) = 0$

and so:

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

Because $v$ was arbitrary in $V$:

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


$(b): \quad$ Define:

$S := W \cap \ker \left({p_1 \left({T}\right)^{a_1} }\right)$
$M := \left\{ {f \left({x}\right) \in K \left[{x}\right] : f \left({T}\right) \left({s}\right) = 0 \forall s \in S}\right \}$

and:

$q \left({x}\right) := gcd \left({M}\right)$

By definition of $W$:

$p_2 \left({x}\right)^{a_2} \cdots p_k \left({x}\right)^{a_k} \in M$

As every element of $S$ is also an element of $\ker \left({p_1 \left({T}\right)^{a_1} }\right)$:

$p_1 \left({x}\right)^{a_1} \in M$

it follows that:

$q \left({x}\right) \mathrel \backslash p_1 \left({x}\right)^{a_1}$

and:

$q \left({x}\right) \mathrel \backslash p_2 \left({x}\right)^{a_2} \dotsm p_k \left({x}\right)^{a_k}$

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

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

Thus, we must have:

$q \left({x}\right) \mathrel \backslash gcd \left \{ {p_1 \left({x}\right)^{a_1}, p_2 \left({x}\right)^{a_2} \cdots p_k \left({x}\right)^{a_k} }\right\} = g \left({x}\right) = 1$

So:

$q \left({x}\right) = g \left({x}\right) = 1$

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

$q \left({x}\right) = 1 = h_1 \left({x}\right) p_1 \left({x}\right)^{a_1} + h_2 \left({x}\right) p_2 \left({x}\right)^{a_2} \dotsm p_k \left({x}\right)^{a_k}$

for some $h_1 \left({x}\right),h_2 \left({x}\right) \in K \left[{x}\right]$.

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 $I \left({s}\right) = s$:

$s = h_1 \left({T}\right) p_1 \left({T}\right)^{a_1} \left({s}\right) + h_2 \left({T}\right) p_2 \left({T}\right)^{a_2} \cdots p_k \left({T}\right)^{a_k} \left({s}\right) = 0$

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

$S = W \cap \ker \left({p_1 \left({T}\right)^{a_1} }\right) = 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 $p \left({x}\right)$ at $T$, one needs to convert constants which may appear in the expression of $p \left({x}\right)$ into transformations in the following way : for example, if $p \left({x}\right) = 2 + x$, then $p \left({T}\right) = 2 I + T$, where $I$ is the identity application $I: V \to V$.

$p_1 \left({x}\right), p_2 \left({x}\right), \dotsc, p_r \left({x}\right)$ are not necessarily of degree $1$. For example, if $K = \R$ and $p \left({x}\right) = x^2 + 1$, then $p \left({x}\right)$ is irreducible on $\R$ and $p_1 \left({x}\right) = p \left({x}\right)$ 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.