# How can I prove that a square matrix is invertible if it satisfies this polynomial equation?

For a 3x3 matrix $C$, it is given that

$$C^3+I=3C^2-C$$

I am then required to prove that $C$ is invertible.

I have attempted a proof, below, but I am not sure it is valid or if there is a better solution.

Attempted proof

$$C^3 + I = 3C^2 - C$$ $$I = - C^3 +3C^2-C$$

If it is assumed that $C^{-1}$ exists then

$$I = C^{-1}(-C^4+3C^3-C^2)$$ If $C^{-1}$ is defined, then $I=C^{-1}C$; therefore test whether

$$C \stackrel{!}{=} -C^4 + 3C^3 - C^2$$ $$0 = -C^4 + 3C^3 - C^2 - C$$ $$C = 0, 1, 1\pm\sqrt{2}$$

Is this at all in the right direction?

-
$C$ is a matrix, how can it be $0,1,1\pm \sqrt{2}$? – vadim123 Jun 13 '14 at 22:46

Note that $$I=-C^3+3C^2-C=C(-C^2+3C-I)$$ Hence $C$ is invertible and $C^{-1}=-C^2+3C-I$.

-

Subtract to get $$I=-C^3+3C^2-C$$ Then factor to get $$I=C(-C^2+3C-I)$$ Now you have $I=CD$, for $D=-C^2+3C-I$. Hence $C$ is invertible.

-

$$C^3+I=3C^2-C$$ $$I=-C^3-3C^2-C$$ $$\det(I)=\det(-C^3+3C^2-C)=\det(C)\det(-C^2+3C-I)$$ Assume $C$ is not invertible, i.e. $\det(C)=0$, then from the previous equation you would obtain $\det(I)=0$, that is a contradiction, since $\det(I)=1$.

-
Quick clean and efficient; I love this. – Geoff Naylor Jun 14 '14 at 0:57
Why prove by contradiction? – Tim Seguine Jun 14 '14 at 10:36
@GeoffNaylor That's a very roundabout way of proving invertibility. Brian's answer is more direct. – Jubobs Jun 14 '14 at 15:23

If $C$ is not invertible, it has a non-trivial null space and hence a non-trivial eigenvector $v$ with eigenvalue $\lambda=0$.

We have $(C^3+I)v=(3C^2-C)v$ whence $(\lambda^3+1)v=(3\lambda^2-\lambda)v$ and setting $\lambda=0$ we see that $v=0$, which is a contradiction.

Easiest (and in fact more general) to use the explicit inverse in the other answers, but this is a way to use the eigenvalues as suggested in your answer.

-

The original assumption implies $C$ annihilates the polynomial $X^3-3X^2+X+1$.

But $X^3-3X^2+X+1=(X-1)(X-\sqrt2-1)(X+\sqrt2-1)$

Therefore, $C$ is diagonalizable, but most importantly its determinant is the product of its eigenvalues, hence $|\det(C)|=1$ and $C$ is invertible.

For the sake of generality, for $n\times n$ matrix, $C$ still annihilates $(X-1)(X-\sqrt2-1)(X+\sqrt2-1)$.

By Primary Decomposition Lemma , $C$ is diagonalizable with eigenvalues $1$, $1-\sqrt{2}$, $1+\sqrt{2}$

Hence it has non-zero determinant.

-

$C$ is a 3x3 matrix, so it's characteristic polynomial is $ax^3 + bx^2 + cx + d$.

A matrix is invertible iff it doesn't have a zero eigenvalue, which occurs iff $d \ne 0$.

Every matrix satisfies it's characteristic polynomial.

Your given polynomial is a 3rd degree polynomial with $d \ne 0$, thus the characteristic polynomial is as well, thus $C$ doesn't have an eigenvalue of $0$, thus it is invertible.

-

We have $C^3+I=3C^2−C$

$\implies I=-C^3+3C^2−C$

$\implies I=C(-C^2+3C−I)=(-C^2+3C−I)C$

if $AB=BA=I$ then $A^{-1}=B$

Then $C^{-1}=(-C^2+3C−I)$

-

Let me add a bit of clarity to what's going on here and/or overcomplicate things needlessly. In the end, we will be able to construct a similar-problem-production-machine that produces these kinds of annoying problems effortlessly!

Okay. Most of the interesting stuff that is going on here can be understood using certain general principles that have nothing to do with polynomials or matrices and everything to do with basic order theory. We'll need a couple of basic order-theoretic concepts. Firstly, that of a minimum.

Definition (minimum). Let $P$ denote a preordered set. Then $a \in P$ is a minimum of $P$ iff for all $b \in P$ we have $a \lesssim b$.

Observation. If $\lambda$ is a minimum of $P$, then for all $a \in P$, we have that $a$ is a minimum of $P$ iff $a \mid \lambda$.

Proposition A0. If $a$ is a minimum of $P$ and $a' \lesssim a$, then $a'$ is a minimum of $P$.

Secondly, that of an inflationary endofunction.

Definition (inflationary). Let $P$ denote a preordered set and $f$ denote an endofunction of $P$. Then $f$ is inflationary iff for all $x \in P$ we have $x \lesssim f(x).$

(This is sometimes called "expansive" rather than "inflationary").

Proposition A1. Inflationary maps reflect minima.

i.e. Suppose $f : P \leftarrow P$ is an inflationary endofunction. Then for all $x \in P$, if $f(x)$ is minimum, then so too is $x$.

Moving right along.

Let $M$ denote a monoid. Then we can make $M$ into a preordered set in the following way.

Definition (divisibility). Given $a,b \in M$, define that $a \mid b$ iff the following two conditions hold.

• There exists $x$ such that $ax=b.$
• There exists $x$ such that $xa=b.$

All our previous ideas apply, just under a different name:

Definition (invertible). Given $a \in M$, define that $a$ is invertible iff it is a minimum of $M$ with respect to divisibility.

Observation. Given $a \in M$, $a$ is invertible iff $a \mid 1$.

Proposition B0. Given $a,b \in M$, if $b$ is invertible and $a \mid b$, then $a$ is invertible.

In particular:

Proposition B1. Given an endofunction $f$ on $M$, if $f$ is inflationary with respect to divisibility, then $f$ reflects invertibility.

It turns out that inflationary endofunctions arise whenever we're dealing with univariate polynomials without a constant term. In particular:

Claim. Let $S$ denote a commutative semiring suppose $p \in S[x].$ Then if $p$ has no constant term, it follows that for all $S$-algebras $A$, the function $[p]_A : A \leftarrow A$ induced by substitution is inflationary with respect to divisibility.

Let us now return to your question. We're given a matrix $C \in \mathbb{R}^{n \times n}$. Rearranging the information a little, we obtain:

$$C^3-3C^2+C=-I$$

So define a function $f : \mathbb{R}^{n \times n} \leftarrow \mathbb{R}^{n \times n}$ as follows: $$f(A) = A^3-3A^2+A$$

Then $f$ is induced by the polynomial $p=x^3-3x+x$. That is, $f = [p]_{\mathbb{R}^{n \times n}}$. But since $p$ has no constant term, hence by the previous claim, we deduce that is $f$ is inflationary with respect to divisibility.

Therefore by Proposition B1, $f$ reflects invertibility.

So the proof goes like so: since $f(C)=-I$, hence $f(C) \mid -I$ (since $\mid$ is a preorder and in particular reflexive), hence $f(C)$ is invertible by Proposition B0. But since $f$ reflects invertibility, hence $C$ is invertible.

Okay, what have we achieved? Well, we've now understood the crap out of why this occurs, and it now becomes possible to produce many similar problem for unsuspecting students. In particular:

Similar-problem production-machine. Write $[p]_{\mathbb{R}^{n \times n}}(C)=U,$ where $p$ is your favorite non-constant univariate polynomial and $U$ is your favorite $n \times n$ invertible matrix. Now do some obnoxious rearranging and call the resulting equation $E$. Problem for students: show that if $E$ holds, then $C$ is invertible.

-