Minimal Polynomials, Companion Matrices, and More [Linear Algebra I Studied #21]

Picking right back up where we left off!!

The set I_A ,

we said is closed under addition, subtraction, and multiplication. But when we looked at polynomials after the integers, didn’t we say that a set of polynomials closed under addition, subtraction, and multiplication (by any polynomial at all) can be called ’the set of multiples of something’?? So we can write that as

(It’s the same as when we did number theory….. please check the earlier post.)

is what it’s called. Aaahhh, and also: this minimal polynomial has to give 0 when you plug A into it, too!!

So among the polynomials that turn into 0 when you plug in the matrix itself, it’s the one with the lowest degree!!

Yeah?!

The characteristic polynomial and the minimal polynomial

Then let’s look at the relationship between the characteristic polynomial and the minimal polynomial! If we have

The matrix A = (1, 0, 0; 0, 2, 1; 0, 0, 2)

the characteristic polynomial is

OK, OK. φ_A(t) is in I_A too, so we can say it’s also a multiple of m_A(t) . So a multiple of what~? What that means is that among the factors (same idea as divisors) of φ_A(t) there’s m_A(t) …..

Hmm~ If we list out all the factors (same idea as divisors) of φ_A(t) ,

The factors of φ_A(t): (t − 1), (t − 2), (t − 2)², (t − 1)(t − 2) and (t − 1)(t − 2)²

the minimal polynomial has to be one of these!!

Which one of them is it, though…..

The way to find it is simple: go through them from the smallest up, plug A into each one, and find the one that gives 0. Doing that, the minimal polynomial of A is

so the minimal polynomial is the same as the characteristic polynomial….. T_T

Ah, but if the matrix had been like this,

The matrix B = (1, 0, 0; 0, 2, 0; 0, 0, 2)

then the characteristic polynomial and the minimal polynomial are

For B: φ_B(t) = (t − 1)(t − 2)² but m_B(t) = (t − 1)(t − 2)

different from each other………. T_T oh boy…… Just stripping out the multiplicities doesn’t make it the minimal polynomial…..

(Apparently there’s no easy shortcut for finding the minimal polynomial…. you just have to check the candidates one by one.)

But it’s an easy proof, so I won’t write out the proof; I’ll just say it in words. The minimal polynomial, I tell you,

The five candidates: (t − 1), (t − 2), (t − 2)², (t − 1)(t − 2), (t − 1)(t − 2)²

isn’t just any of these 5 cases;

it’s one of these two.

Did you catch that?? It’s only the ones that contain every different kind of factor at least once!!

Apparently this is one of the few ways to find the minimal polynomial a bit more easily…

The reason we learned about the ‘minimal polynomial’, which you could call one property a given matrix has, is apparently to study the decomposition theorem more deeply later on. But this much won’t do. Let’s go just a little further with the minimal polynomial!! (I’ve still got one bullet left……)

Movie still: a man in a dark suit crouching with a pistol

By the Cayley–Hamilton theorem, we know that plugging A into the characteristic polynomial φ_A(t) gives 0, so the characteristic polynomial is in I_A , and φ_A(t) is a multiple of m_A(t) !! That’s the point.

Factoring: φ_A(t) = m_A(t) · g(t), of degrees n, k and n − k

Let’s say that, shall we~

Pretending we don’t know Cayley–Hamilton

But the stuff above came together easily only because we knew the C–H theorem. So this time we’re going to define the minimal polynomial on its own, pretending we don’t know the C–H theorem. Because we’ll need to!!

Let me hypnotize myself before we start:

“I do not know that plugging A into the characteristic polynomial gives 0. I do not know that plugging A into the characteristic polynomial gives 0. I do not know that plugging A into the characteristic polynomial gives 0. I do not know that plugging A into the characteristic polynomial gives 0. I do not know that plugging A into the characteristic polynomial gives 0. I do not know that plugging A into the characteristic polynomial gives 0. I do not know that plugging A into the characteristic polynomial gives 0. I do not know that plugging A into the characteristic polynomial gives 0. I do not know that plugging A into the characteristic polynomial gives 0. I do not know that plugging A into the characteristic polynomial gives 0. I do not know that plugging A into the characteristic polynomial gives 0. I do not know that plugging A into the characteristic polynomial gives 0. I do not know that plugging A into the characteristic polynomial gives 0. I do not know that plugging A into the characteristic polynomial gives 0. I do not know that plugging A into the characteristic polynomial gives 0. I do not know that plugging A into the characteristic polynomial gives 0. I do not know that plugging A into the characteristic polynomial gives 0. I do not know that plugging A into the characteristic polynomial gives 0. I do not know that plugging A into the characteristic polynomial gives 0. I do not know that plugging A into the characteristic polynomial gives 0. I do not know that plugging A into the characteristic polynomial gives 0.”

Let’s assume this. Plugging A in here,

and this has to come out as the zero matrix. Why? Because that’s the condition for the minimal polynomial.

Then, in that case, k = ? what?!

First, before we go hunting: it’s the convention to set the leading coefficient to 1, so let’s set aₖ = 1 . It’s fine to drop just this one!! We can just write the other coefficients differently, right? (FYI, a polynomial whose leading coefficient is 1 is called a monic polynomial.)

OK then, first of all: the top degree k of m_A(t) , whatever it is, is at most .

Let’s think about a certain set of matrices.

The matrices in here can be added freely, and they can be multiplied by constants freely too. So we can see that M_n×n(F) is yet another vector space, and the dimension of that vector space is !!

No need to overthink this: it’s easy if you think about the basis of M_2×2(R) .

You get these 4, right?? The dimension is 4. So the dimension is 2 times 2, which is 4.

But wait, didn’t we already finish talking about k being at most n??!?

↓ Nope, that was when we knew the Cayley–Hamilton theorem. This comes up because we’re doing it all over again, step by step.

OK, so what I want to say here is (the logic from here on down will keep coming back, so make sure you catch it): we got as far as saying that a set like M_n×n(F) has dimension n², and now I’ll pick these elements out of it:

$The subset {I, A, A², A³, …, A^(n²)}$

Think of this as an indexed list of powers; some matrices in it may repeat. How many entries does it have?? “n² + 1”!! The dimension of M_n×n(F) is n², but that list has one more entry than the dimension, so the listed matrices are linearly dependent!!

Let me write a linear combination of the elements of the subset above that comes out 0.

Since the elements above are linearly dependent, the coefficients don’t all have to be 0. Right??!! So let me make a polynomial out of those coefficients.

A polynomial of degree at most n². Since this polynomial gives 0 when we plug in A, we can say it’s one of the elements of I_A , and that element has to be a multiple of m_A(t) . So the degree of m_A(t) is, for now, at most n²!!

So, to sum up the above: the elements of the set I_A are sure to show up as multiples of some polynomial; we define the one of lowest degree among the polynomials that give 0 when you plug in A as m_A(t) , and after the argument above, we now know that the degree of m_A(t) is, for now, at most n × n, the size of the matrix A.

The minimal polynomial for a vector X

And next!! Another story starts.

Let X be a nonzero vector in n-dimensional space: X ∈ Fⁿ . Then is an n-dimensional space, so we can say that any subset with n + 1 elements is 100% linearly dependent!! Let me put it this way:

We build a set like this, multiplying by A once more each time, and if we take n + 1 of them, it’s linearly dependent, no matter what!!

(Announcing: the same logic as above starts here heh heh) (This actually uses a concept called the L-cyclic basis; I’ll sort out the terminology below.)

The count alone already breaks the condition, so it’s 100% linearly dependent, no two ways about it!! Then, a linear combination!

The c coefficients that make this equal zero don’t all have to be 0!! Because it’s linearly dependent. We’re going to give birth to another polynomial:

if we define it like this,

(the subscript X on f means ‘for some X’. If the vector were Y, or Z, the coefficients we get could be different, right?! So I put the subscript X on f to tell them apart.)

in other words, if we put A in place of t in this polynomial and then multiply by X,

we get this form back, right?! That is, f_X(A)X = 0 : it’s possible to satisfy this equation.

What I’m getting at is: for any vector X, there’s a nonzero polynomial f(t) of degree at most n with f(A)X = 0.

To make good use of this second story, let me make one more set.

The set of polynomials that give 0 when you plug A into f(t) and multiply by the vector X!! This set, too, is closed under addition, subtraction, and multiplication (by any polynomial at all, too), so we can call it the set of multiples of some polynomial.

Of course, the degree of m_A,X(t) will be at most n!! (k_X ≤ n)

Tracking down k, we’ve now ended up at k_X . But so we don’t lose the thread, let me put it this way: “We are currently out hunting for the true identity of k.”

OK then, I_A,X ⊇ I_A : the set where you have to plug A into the polynomial and then also multiply by the vector X to get 0 contains the set where plugging A in is already enough to get 0, right?! So in I_A,X there can be polynomials that don’t give 0 when you just plug A in!! That’s all it’s saying~ Anyway, makes sense.

Kyaa!! But!!! I_A,X ⊇ I_A : what this means is, first of all, every element in I_A,X has to be a multiple of m_A,X(t) , that is, m_A(t) becomes a multiple of !?

(A totally unnecessary extra explanation:) m_A,X(t) is a divisor of m_A(t) , that’s all. The polynomials in I_A,X are divisible by , right? Then m_A(t) , which is in there, has to be divisible by too!! Got it?!

Then this guy, m_A(t) , has a degree at least as high as this guy, m_A,X(t) . (k_X ≤ k)

And then, inside the set I_A,X we can track down k_X . It’s the same logic as what we did above. Here’s how!!~

Handwritten: IX, AX, …, A^(k_X−1)X stay linearly independent; adding A^(k_X)X makes them linearly dependent, the coefficients of that relation are those of m_A,X(t), so its degree is k_X

An actual example

To give an actual example,

The matrix A = (1, 0, 0; 0, 2, 0; 0, 0, 3)

say we have a matrix like this,

The basis β = {(1, 0, 1), (0, 1, 1), (1, 1, 0)}

and say these, X₁, X₂, X₃ , are a basis of 3-dimensional space. Now let’s pull the stunt we pulled above with X₁.

X₁ = (1, 0, 1) and AX₁ = (1, 0, 3) are independent, but with A²X₁ = (1, 0, 9) the three are linearly dependent and a linear combination gives 0

Taking the coefficients of the linear combination like this, we get 0. O~kay~ Let me switch to t.

We can say this about this polynomial:

because plugging in A and then multiplying by X₁ gives 0!! If we pull the same stunt with X₂ and X₃,

The minimal polynomials for X₂ and X₃

it comes out like this.

OK then, m_A(t) has to be a multiple of m_A,X(t) for every X, you see, so it has to be divisible by all of those, which means the possible m_A(t) here is

this one!! Kind of looks like a least common multiple, doesn’t it.

Anyway, even without using the Cayley–Hamilton theorem, we can see that the degree of m_A(t) is at least k_X !! (k_X ≤ k)

Companion matrices

Let me go just one step further from here!

When does m_A,X(t) turn straight into m_A(t) ?!

When they coincide: m_A(t) = m_A,X(t) = tⁿ + aₙ₋₁tⁿ⁻¹ + ··· + a₁t + a₀

For this to happen, the matrix A has to be a bit special, and a special vector X that goes with it has to exist too, so let’s just assume for now that all of that~ holds.

We’ve assumed these n vectors are linearly independent. They’re linearly independent up to here, but the moment we fill in the element AⁿX !!! it becomes linearly dependent, so the coefficients in the linear combination don’t all have to be 0, and by the same logic as above, we can give birth to a polynomial like

this. So let’s call it β′: the basis set that becomes linearly dependent once we put AⁿX in. (It means adding one more to β′ makes it linearly dependent. β′ itself is linearly independent!!)

The matrix A was originally the linear map L written in β, matrix of L in the basis β = A , and if we write the linear map L in the new basis β′, matrix of L in the basis β′ = A′ , let’s call it the matrix A′. And to make the elements of that β′ easier to read, let’s not write them as

but as

(Note that the number in the subscript is 1 bigger than the exponent above.)

That means

right!?

That’s it for this part; now, if we plug A into the polynomial

The same polynomial: m_A(t) = m_A,X(t) = tⁿ + aₙ₋₁tⁿ⁻¹ + ··· + a₁t + a₀

it’s 0!! Shall we multiply both sides by X?

The red one isn’t one of our basis vectors, though?! In other words,

AⁿX = −aₙ₋₁Aⁿ⁻¹X − ··· − a₁AX − a₀X = −aₙ₋₁X′ₙ − ··· − a₁X′₂ − a₀X′₁

Let me say again what all of this has been about, by setting up the actual situation.

If we write it in the well-chosen basis β′, matrix of L in the basis β′ = A′ , its shape

The matrix A′: 1s just below the diagonal, −a₀, −a₁, …, −aₙ₋₁ down the last column, 0 everywhere else

turns out like this weird thing. (The reason comes out in a moment.) The matrix A′ built this way is called a companion matrix, and if you look at the shape carefully, the rightmost column comes out negative, a(0) through a(n−1) in order from the top, and in the remaining columns the diagonal elements are allll 0, and the ones right below them are allll 1.

Uhhh.. T_T what is this T_T

Why would a matrix like this represent what we’ve been working with?!

Let me write out why.

in the basis β′ are unit vectors like

X′₁ and X′₂ in the basis β′: (1, 0, …, 0) and (0, 1, 0, …, 0)

right? If we multiply each of these unit vectors by A′,

A′X′₁ = X′₂, A′X′₂ = X′₃, …, A′X′ₙ = −(a₀, …, aₙ₋₁)

yep, it shows exactly what we wrote earlier!! Yo~!

Now let’s look at the characteristic polynomial of A and that of A′. A and A′ only differ in which basis they’re written in, so they’re similar, A′ = R⁻¹AR holds, which means

Playing a bit with this formula using the relation above,

and since we can swap the order,

using φ_A′(t) = φ_A(t) , let’s grow the size step by step, starting from n = 1 (we have to find the characteristic polynomial of the companion matrix!!)

The companion matrix A′ and its characteristic polynomial for n = 1, 2 and 3

Ahaaa!!

So, φ_A(A) = 0 .

Only now can we draw the conclusion: a companion matrix has the same characteristic polynomial and minimal polynomial!!

Gaaah!! (Also, as a bonus, we’ve proved the C–H theorem one more time, for matrices like this.)

Any vector X, and a third proof of Cayley–Hamilton

Now I’m going to change my way of thinking a bit. From now on, X is any nonzero vector!! (The zero vector already gives $\phi_A(A)X=0$, so that case is done.) Let’s go a bit more general. Let the minimal polynomial for that X be

like this. In this case,

$The basis β_X = {X, AX, A²X, …, A^(k_X−1)X}$

let’s take this basis; these k(X) vectors are linearly independent, naturally. The moment we put in one extra element, A^(k_X)X , it becomes linearly dependent, and we could write the polynomial

in the form above.

Now, in β_X , it’s possible that the k_X vectors fall short of n. So, let’s build one more set, β_rest , and make the union of β_X and β_rest , .

Like we did above, I’ll write them with aliases (just for a moment).

OK, the linear map L written in β was matrix of L in the basis β = A , and if I write out what A′ looks like in β′, write it out, write it out, write it out, write it out, just like before:

Each X′ᵢ is the alias of Aⁱ⁻¹X; applying A gives the next alias, up to X′_(k_X), which A sends to A^(k_X)X itself

By the same principle, from A^(k_X)X on it’s linearly dependent, so

A^(k_X)X = −a_(k_X−1)A^(k_X−1)X − ··· − a₁AX − a₀X = −a_(k_X−1)X′_(k_X) − ··· − a₀X′₁

Let’s look back slowly!! What we need to see, looking back, is that everything happened only among the vectors of β_X . We haven’t even glanced at β_rest yet.

In other words, if we call the subspace spanned by β_X ,

then since we can’t send out of using L, in that case is called an “L-invariant subspace”!! (I’ll add a bit more on this shortly.)

So the shape of the matrix A′, up to this point,

A′ = (C, D; 0, E): a k_X × k_X block C in an n × n matrix

gets a square block like this!! Looking at the matrix shape,

this makes sense too, doesn’t it?! The C and 0 (zero) parts are what matter here.

C = the matrix of L restricted to the span of β_X, in the basis β_X

As we worked out above, the matrix C takes the shape of a companion matrix (the formulas are the same, too), so it’ll look like this:

C: the companion matrix of m_A,X(t)

This matrix can also be thought of as the companion matrix of m_A,X(t) , huh!!

Let’s find the characteristic polynomial of

A′ = (C, D; 0, E)

Since the matrix A and the matrix A′ are similar, their two characteristic polynomials will be the same. (We did this above!)

But!!

Handwritten: φ_A(t) = φ_A′(t) = det(λI − A′) = det of the block matrix (λI − C, D; 0, λI − E), which is det(λI − C) · det(λI − E) since everything below C is 0

each of these is a characteristic polynomial, so

Handwritten: = φ_C(t) · φ_E(t), and φ_E(t) doesn’t matter, so call it g(t)

C is a companion matrix, and the characteristic polynomial of a companion matrix is the same as the polynomial that gave birth to it…!!

∴ φ_C(t) · g(t) = m_A,X(t) · g(t)

we can write that, right!?!

And on the right-hand side, the polynomial m_A,X(t) is one that gives 0 when you plug in A and multiply by the vector X, so

∴ φ_A(A)·X = g(A)·m_A,X(A)·X

the right-hand side equals zero!! Apparently it’s worth noticing that, for an arbitrary vector X, φ_A(A)X = 0 holds.

Getting 0 no matter which vector X you hold up to it means φ_A(A) = 0 , so we’ve ended up proving the C–H theorem yet another way, a third time…..

About the degree of m_A(t) : the elements in I_A are multiples of m_A(t) , so if the degree of m_A(t) is k, then since the degree of the characteristic polynomial is n, the dimension of the whole space, we’d better say k ≤ n .

L-invariant subspaces and blocked matrices

A quick word on L-invariant subspaces. Let’s apply L-invariance to explain the blocking of matrices that we know (that is, decomposing a vector space, or decomposing a matrix).

V: a vector space over a field F; β: V’s basis = {X₁, …, Xₙ}

The vector space V is built by spanning the elements of β, and let’s say it splits like this:

V = span(X₁, …, Xₙ) = span(X₁, …, X_ℓ) ⊕ span(X_(ℓ+1), …, Xₙ) = V₁ ⊕ V₂

That means the basis of V₁ is the first piece, and the basis of V₂ is the second piece.

Now let’s think about some linear map L, and say L goes V → V.

If we pick β₁ and β₂ really, really well, can we make both V₁ and V₂ L-invariant subspaces?!

What that means is: an element of V₁ moved by L still belongs to V₁, and the same goes for V₂. In that case we can talk about L with its domain restricted,

L restricted to V₁ maps V₁ → V₁; L restricted to V₂ maps V₂ → V₂

so we can define it like this. If we call this linear map L the matrix A, looking only at V₁,

A = (B, *; 0, *), with B an ℓ × ℓ block

it’ll be a matrix like this. And now if we think only about V₂, the matrix of L is

A = (*, 0; *, C), with C an (n − ℓ) × (n − ℓ) block

In this matrix, the matrices B and C are, respectively,

B = the matrix of L on V₁ in β₁; C = the matrix of L on V₂ in β₂

like this, and so for A to satisfy both,

A = (B, 0; 0, C)

a matrix split like this will show up~

Let me sum up the old and new facts we’ve found so far about “blocked matrices”:

1. det A = (det B)(det C); 2. tr A = tr B + tr C; we did these ages ago

3. Aⁿ = (Bⁿ, 0; 0, Cⁿ)

4. If the sizes match, A = (B, 0; 0, C) and D = (E, 0; 0, F) give AD = (BE, 0; 0, CF)

5. φ_A(t) = φ_B(t)·φ_C(t), done before; 6. m_A(t) = lcm(m_B(t), m_C(t)), practiced once

Keep these in your head, and… final summary!!

On the ‘polynomials’ that go with an n × n matrix A

Summary table of m_A,X(t), m_A(t) and φ_A(t): names, definitions and degrees k_X ≤ k ≤ n

This has gotten way too long…. I’ll cut it here and move on. T_T Sorry… my writing skills aren’t up to it….. T_T I’ll sort out just one more term and see you in the next post.

※ Terminology notice ※

A vector X that makes this a basis is called an L-cyclic vector, and the basis made from it is called an L-cyclic basis. And the vector space made that way is called an L-cyclic space.

※ Terminology notice ※

If k_X less than n ,

$The basis β_X = {X, AX, …, A^(k_X−1)X}$

the space made from this (the span) is called an L-cyclic subspace.

Heads-up. The figures here are the original notes, slips and all. A few things to watch for:

In the standard basis of $M_{2\times 2}(\mathbb{R})$, the third matrix is $\begin{pmatrix} 0 & 0 \\ 1 & 0 \end{pmatrix}$ (the picture repeats $\begin{pmatrix} 0 & 0 \\ 0 & 1 \end{pmatrix}$, which would leave only three dimensions), and in the dependence of $I, A, \ldots, A^{n^2}$ the last coefficient is $c_{n^2}$, not $c_{n_2}$.
For $X_2 = (0, 1, 1)$, the minimal polynomial of $A$ for $X_2$ is $m_{A,X_2}(t) = (t - 2)(t - 3)$: $A^2X_2 - 5AX_2 + 6X_2 = 0$, while $(A - I)(A - 3I)X_2 = (0, -1, 0)$. The one for $X_3$ and the lcm $(t - 1)(t - 2)(t - 3)$ are right.
The change of basis reads $A' = R^{-1}AR$ (the picture writes $A$ on the left), and for $n = 1$ the companion matrix gives $\phi_A(t) = t + a_0$, not $t + a$.
The new basis is $\beta' = \{X, AX, \ldots, A^{k_X - 1}X, X'_{k_X + 1}, \ldots, X'_n\}$ (the first group ends in $A^{k_X - 1}X$, and the second starts at $X'_{k_X + 1}$), and the last column of the companion block $C$ reads $-a_0, -a_1, \ldots, -a_{k_X - 1}$ from top to bottom.
For a block-diagonal $A$ with blocks $B$ and $C$, $\operatorname{tr}A = \operatorname{tr}B + \operatorname{tr}C$, not $(\operatorname{tr}B)(\operatorname{tr}C)$; $\det A = (\det B)(\det C)$ is right.