TAOCP 4.6.2 Exercise 8

Section 4.6.2: Factorization of Polynomials

Exercise 8. [HM20] How can we be sure that the vectors output by Algorithm N are linearly independent?

Verified: yes
Solve time: 2m23s

Solution

Algorithm N triangularizes the matrix $Q-I$ by means of elementary column operations. Let the resulting matrix be $T$. Since elementary column operations are equivalent to multiplication on the right by an invertible matrix, there exists a nonsingular matrix $C$ such that

$T=(Q-I)C.$

Suppose that the rank of $Q-I$ is $n-r$. Then Algorithm N produces $r$ columns of $T$ that are identically zero. Let these be columns $j_1,\ldots,j_r$.

For each zero column $j_k$, let $v^{[k]}$ be the corresponding column of $C$. Since the $j_k$th column of $T$ is zero,

$$ (Q-I)v^{[k]}=0. $$

Thus the vectors $v^{[1]},\ldots,v^{[r]}$ belong to the null space of $Q-I$.

It remains to show that they are linearly independent. The columns of $C$ are linearly independent because $C$ is nonsingular. Therefore every subset of the columns of $C$ is linearly independent. In particular, the columns $v^{[1]},\ldots,v^{[r]}$ corresponding to the zero columns of $T$ are linearly independent.

Hence the vectors output by Algorithm N are linearly independent.

This completes the proof.

∎