# Finding the Dimension of a Matrix Polynomial: $W$ = { $p(B)$ : $p$ is a polynomial with real coefficients}

Let $W = \{ p(B) : p \text{ is a polynomial with real coefficients}\}$, where $$B= \begin{pmatrix} 0 & 1 & 0\\ 0 & 0 & 1\\ 1 & 0 & 0 \end{pmatrix}$$

Which of the following possibilities presents the tightest bounds on the dimension $d$ of the vector space $W$?

1. $4 ≤ d ≤ 6$
2. $6 ≤ d ≤ 9$
3. $3 ≤ d ≤ 8$
4. $3 ≤ d ≤ 4$
-
Could you phrase your post as a question, and also tell us what you have tried so far? – Trevor Wilson Dec 19 '12 at 6:42
I edited this post to turn it into a question. I may edit it further to provide some motivation and/or context. – Robert Lewis Jun 3 '15 at 22:37

First, check that $W$ is a subspace: If $p_1(B),p_2(B) \in W$, then $(p_1+p_2)(B) \in W$ and if $p(B)\in W$, then $(\lambda p)(B) \in W$. The dimension of a subspace is the maximum number of linearly independent vectors (or on this case, matrices, which can also be viewed as vectors)

The Cayley Hamilton theorem tells us that the characteristic polynomial $\chi(x) = \det (xI -B)$ of $B$ satisfies $\chi(B) = 0$.

Since the characteristic polynomial of $B$ is $\chi(x)=x^3-1$, Cayley Hamilton gives (also by direct computation) $B^3 - I=0$, or $B^3 = I$. In particular, we have $B^k = B^{k \text{ mod } 3}$ and so any power of $B$ can be written as one of $I,B,B^2$, and hence if $p$ is a polynomial, we can write $p(B) = p_0I+p_1B+p_2 B^2$ for some $p_0,p_1,p_2$. That is, $I,B,B^2$ form a spanning set for $W$.

Hence $W \subset \operatorname{sp} \{I,B,B^2\}$, and we see that $d=\dim W \le 3$.

To see that $d=3$, we need to show that $I,B,B^2$ are linearly independent.

Note that $B^2 = \begin{bmatrix} 0 & 0 & 1 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \end{bmatrix}$. Now suppose $\alpha_0 I+\alpha_1 B + \alpha_2 B^2 = 0$. Since $B_{11} = (B^2)_{11} = 0$, it follows that $\alpha_0 = 0$. Since $I_{31} = (B^2)_{31} = 0$, it follows that $\alpha_1 = 0$, and since $B^2 \neq 0$, it follows that $\alpha_2 =0$. Hence they are linearly independent and so $I,B,B^2$ form a basis for $W$, and so $d=3$.

-
I suspect the OP may not quite understand what it means that two matrices are linearly independent. – Andrés E. Caicedo Dec 19 '12 at 6:43
Then dimension of $W$ would be out of reach? (But, point taken, I will elaborate.) – copper.hat Dec 19 '12 at 6:43
That's what I would imagine. – Andrés E. Caicedo Dec 19 '12 at 6:45
@JonasMeyer: Yes, thanks. Loose writing on my part. Will correct. – copper.hat Jun 3 '15 at 21:03

$B$ represents a rotation by $2\pi/3$ about the axis $(1,1,1)^\top.$ we also claim that $$\{I, B, B^2\} \text{ is linearly independent. }$$ proof of the claim: suppose $$aI + bB + cB^2 = 0$$ multiplying on the right by $(1,0,0)^\top$ gives $$a(1,0,0)^T + b(0,0,1)^\top+c(0,1,0)^\top = 0 \implies a = 0, b = 0, c = 0.$$ this proves the claim. therefore a basis for $W$ is $\{I, B, B^2\}$ and its dimension is $3.$

-
Nice answer, endorsed! But how do we know, as claimed, and as on your whole argument depends, that your first sentence holds? (I already know the answer to this, but I think it would enhance your answer to include it.) Cheers! – Robert Lewis Jun 3 '15 at 22:01
@RobertLewis, thanks. you really don't need the geometrical interpretation of $B$ for the result to hold. one can verify that $(1,1,1)$ is fixed by $B$ and the angle between $u$ in the plane $x + y + z = 0$ and $Bu$ is $2\pi/3.$ – abel Jun 3 '15 at 22:09
I guess you' d do that by looking at $\langle b, Bu \rangle / ( \Vert u \Vert \Vert Bu \Vert)$? Still, it would be nice to see it written up with your customary elegance! – Robert Lewis Jun 3 '15 at 22:12
@RobertLewis, being a little sarcastic there? – abel Jun 3 '15 at 22:13
In fact, no. I've read and respected many of your answers! My complement is genuine! – Robert Lewis Jun 3 '15 at 22:14

Here's a somewhat more ring-theoretic approach; though a bit long-winded, I believe it has certain advantages: first, it does not depend in an essential way on the specific structure of the matrix $B$; any $B$ satisfying (4)-(7) below will give rise to the same conclusion; second, from this abstract viewpoint, it is easier to see how the question may be generalized to other matrices; third, it avoids a lot of explicit matrix computation, which I for one don't find the most enjoyable of mathematical activities.

Consider $\Bbb R[B]$, the $\Bbb R$-algebra of real polynomials in the matrix $B$; it is clearly a subalgebra of $M_3(\Bbb R)$, the full algebra of $3 \times 3$ matrices with coefficients in $\Bbb R$. Furthermore, we have in the usual way a (pretty) natural homomorphism $\theta:\Bbb R[x] \to \Bbb R[B]$ defined by

$\theta(\sum_0^n c_i x^i) = \sum_0^n c_i B^i \in \Bbb R[B] \tag{1}$

for all $\sum_0^n c_i x^i \in \Bbb R[x]$, where $\Bbb R[x]$ is as usual the ring of polynomials in $x$ with real coefficients. That $\theta$ is in fact an algebra, hence a ring, homomorphism is easy to see; so easy, in fact, that I shall omit the details of the verification; those interested in such details might find it helpful to consult Sheldon Axler's little book, Linear Algebra Done Right, where in the section of Chapter 5 titled "Polynomials Applied to Operators" he explains the whole stuck in less than two pages. This book is familiar to many MSE users, Yours Truly included; I found my nearly brand new copy on a sidewalk here in Oakland, California, where people often leave useful items free for the taking.

These things being said, we return our attentions to the map $\theta$ itself.

It is clear that $\theta$ is surjective, for given $\sum_0^n c_i B^i \in \Bbb R[B]$, taking $\sum_0^n c_i x^i \in \Bbb R[x]$ yields (1).

We compute

$\ker \theta = \{ p(x) \in \Bbb R[x] \mid \theta(p(x)) = p(B) = 0 \}. \tag{2}$

In order to do this we will need to introduce several properties of the given matrix

$B = \begin{bmatrix} 0 & 1 & 0 \\ 0 & 0 & 1 \\ 1 & 0 & 0 \end{bmatrix}; \tag{3}$

we then have:

$B^3 = I; \tag{4}$

$(B - I)(B^2 + B + I) = 0; \tag{5}$

$B - I \ne 0; \tag{6}$

$B^2 + B + I \ne 0. \tag{7}$

(4) holds by direct calculation; (5) follows from (4) via

$(B - I)(B^2 + B + I) = B^3 - I = 0; \tag{8}$

(6) binds since it is equivalent to $B \ne I$, which is evident from inspection of $B$; (7) is again verified by direct computation, noting that

$B^2 = \begin{bmatrix} 0 & 1 & 0 \\ 0 & 0 & 1 \\ 1 & 0 & 0 \end{bmatrix} \begin{bmatrix} 0 & 1 & 0 \\ 0 & 0 & 1 \\ 1 & 0 & 0 \end{bmatrix} = \begin{bmatrix} 0 & 0 & 1 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \end{bmatrix}; \tag{9}$

thus

$B^2 + B = \begin{bmatrix} 0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \end{bmatrix} \ne -I. \tag{10}$

(4)-(7) are the only properties of $B$ we shall need; by their virtue, we may avoid further algebraic manipulation of the entries of $B$ per se, thus sparing ourselves the vicissitudes of extensive arithmetic.

We observe that

$(x^3 - 1) \subset \ker \theta, \tag{11}$

where $(x^3 - 1)$ is the principal ideal in $\Bbb R[x]$ generated by $x^3 - 1$; that is

$(x^3 -1) = \{ f(x)(x^3 - 1) \mid f(x) \in \Bbb R[x] \}; \tag{12}$

(11) follows from (4) and (12) since

$\theta(f(x)(x^3 -1)) = \theta(f(x)) \theta(x^3 - 1) = f(B)(B^3 - I) = 0. \tag{13}$

Having (11), we take things one step further and show that in fact

$\ker \theta = (x^3 - 1). \tag{14}$

We recall that $\Bbb R$ being a field, $\Bbb R[x]$ is a Euclidean domain, hence a prinicpal ideal domain; thus

$\ker \theta = (k(x)) \tag{15}$

for some $k(x) \in \Bbb R[x]$; by (11),

$x^3 - 1 \in \ker \theta = (k(x)); \tag{16}$

thus

$x^3 - 1 = q(x) k(x) \tag{17}$

for some $q(x) \in \Bbb R[x]$; since

$\deg q(x) + \deg k(x) = \deg x^3 - 1 = 3, \tag{18}$

if follows that

$0 \le \deg k(x) \le 3; \tag{19}$

also, in $\Bbb R[x]$ we note that $x^3 - 1$ may be factored as:

$x^3 - 1 = (x - 1)(x^2 + x + 1), \tag{20}$

with both $x - 1$ and $x^2 + x + 1$ irreducible in $\Bbb R[x]$; $x - 1$ is irreucible since is of degree one; on the other hand, if $x^2 + x + 1$ were reducible in $\Bbb R[x]$ we could write

$x^2 + x + 1 = (x - \alpha)(x - \beta) \tag{21}$

with $\alpha, \beta \in \Bbb R[x]$; but the zeros of $x^2 + x + 1$ are, by the quadratic formula

$\alpha, \beta = \dfrac{1}{2}(-1 \pm i\sqrt{3}) \notin \Bbb R; \tag{22}$

it follows that $x^2 + x + 1$ cannot expressed as the product of linear factors in $\Bbb R[x]$; hence it is irreducible; since as has been noted $\Bbb R[x]$ is a principal ideal domain, its irreducibles and primes coincide, implying that $x - 1$ and $x^2 + x + 1$ are both prime in $\Bbb R[x]$.

Turning again to (17), and using (20), we write

$(x -1)(x^2 + x + 1) = q(x)k(x); \tag{23}$

recalling once again that $\Bbb R[x]$ is a principal ideal domain, we invoke the standard result that unique factorization into primes/irreducibles holds in $\Bbb R[x]$; applying this conclusion to (23) implies that there are precisely four possibilities for $k(x)$, in accord with whether or not none, one, or both of the primes $x - 1$, $x^2 + x + 1$ occurs as a divisor; they are:

$k(x) = 1; q(x) = (x - 1)(x^2 + x + 1) = x^3 - 1; \tag{24}$

$k(x) = x - 1; q(x) = x^2 + x + 1; \tag{25}$

$k(x) = x^2 + x + 1; q(x) = x - 1; \tag{26}$

and

$k(x) = (x - 1)(x^2 + x + 1) = x^3 - 1; q(x) = 1. \tag{27}$

We systematically eliminate candidates (24)-(26): $k(x) = 1$ implies $\ker \theta = (1) = \Bbb R[x]$ or $\theta = 0$, which contadicts (1); $k(x) = x - 1$ implies $B - I = \theta(x) - \theta(1) = \theta(x - 1) = 0$, in opposition to (6); likewise $k(x) = x^2 + x + 1$ yields $B^2 + B + I = 0$, prohibited by (7); we are left with $k(x) = x^3 - 1$, whence

$\ker \theta = (x^3 - 1). \tag{28}$

By (28) and the fact that $\theta$ is an epimorphism, we see that

$\tilde \theta: \Bbb R[x]/ \ker \theta \cong \Bbb R[B], \tag{29}$

where $\tilde \theta:\Bbb R[x]/ \ker \theta \to \Bbb R[B]$ is the homomorphism induced by $\theta$. We have shown that the isomorphism $\tilde \theta$ referred to in (29) is an isomorphism of algebras, i.e., it isomorphically maps the both the ring and vector space structure of $\Bbb R[x] / \ker \theta$ to that of $\Bbb R[B]$. That this is so follows from the facts that (i.) $\theta$ itself, in addition to being a ring homomorphism, is also a linear map of $\Bbb R[x]$ onto $\Bbb R[B]$, and (ii.), $\ker \theta$ is a linear subspace of $\Bbb R[x]$: for any $a \in \Bbb R$ and any $p(x) \in \ker \theta$, we easily see from (1) that

$\theta(ap(x)) = ap(B) = 0; \tag{30}$

thus $ap(x) \in \ker \theta$, and $\ker \theta$ is a claimed a (vector) subspace of $\Bbb R[x]$. We thus conclude that the induced map $\tilde \theta$ of (29) is an algebra isomorphism, preserving both the ring and vector space structures of $\Bbb R[x] / \ker \theta$. And from this we further conclude that the dimension of $\Bbb R[B]$ over $\Bbb R$ is equal to that of $\Bbb R[x]/\ker \theta$.

It thus remains to evaluate $\dim (\Bbb R[x] / \ker \theta)$ over $\Bbb R$; but this is easy: from the Euclidean algorithm, we have that the quadratic polynomials $\alpha x^2 + \beta x + \gamma$ form a complete set of coset representatives of $\Bbb R[x] / \ker \theta$, since for any $p(x) \in \Bbb R[x]$ we may write

$p(x) = q(x)(x^3 - 1) + r(x) \tag{31}$

for some unique $q(x), r(x) \in \Bbb R[x]$ with $r(x) = 0$ or $\deg r(x) < 3$; (31) may also be written

$p(x) - r(x) = q(x)(x^3 - 1) \in (x^3 - 1) = \ker \theta. \tag{32}$

If we denote by $\overline{p(x)}$ the coset $p(x) + \ker \theta \in \Bbb R[x] / \ker \theta$, then according to (32),

$\overline{p(x)} = \overline{r(x)}, \tag{33}$

since

$\ker \theta = (x^3 - 1 ) = 0 \in \Bbb R[x] / \ker \theta \tag{34}$

is the additive identity, or zero element, of $\Bbb R[x] / \ker \theta$.

Also,

$\overline{r(x)} = \overline{\alpha x^2 + \beta x + \gamma} = \alpha \bar x^2 + \beta \bar x + \gamma. \tag{35}$

From (33) and (35) we immmediatly conclude that $\dim \Bbb R[x] / \ker \theta$ it most $3$ over $\Bbb R$; since it is spanned by $\bar 1$, $\bar x$, $\bar x^2$; furthermore, these three elements of $\Bbb R[x] / \ker \theta$ are linearly independent over $\Bbb R$, since

$\alpha \bar x^2 + \beta \bar x + \gamma = 0 \in \Bbb R[x]/\ker \theta \tag{36}$

implies

$\alpha x^2 + \beta x + \gamma \in \ker \theta = (x^3 - 1); \tag{37}$

however, the degree of every non-zero polynomial $f(x) = q(x)(x^3 - 1)$ in $(x^3 - 1)$ is at least $3$, since it has $x^3 - 1$ as a factor; thus we must have $\alpha = \beta = \gamma = 0$ and $\bar 1$, $\bar x$, $\bar x^2$ are linearly independent in $\Bbb R[x] / \ker \theta$, whence $\dim \Bbb R[x]/\ker \theta = 3$ over $\Bbb R$; the same is thus true of $\Bbb R[B]$.

-