# Open Problem: Application of Cayley-Hamilton Theorem

DISCLAIMER: This problem is explained properly on my YouTube channel, at the following link: PROBLEM: Analysis of 2x2 Matrices using Cayley-Hamilton Theorem. I suggest you watch this before looking below.

Before I start, let's recall the Cayley-Hamilton Theorem:

Theorem (Cayley-Hamilton Theorem) If $A$ is a square matrix and $c_A(\lambda) = \det(\lambda I-A)$ is its characteristc polynomial, then (allowing for matrices as the polynomial variable) $c_A(A) = \bf{0}$, where $\bf{0}$ is the zero square matrix.

Suppose now that $A$ is the following 2 x 2 matrix:

$A = \begin{pmatrix} a & b\\ c & d \end{pmatrix}$

Note that the trace (denoted by $t$) and determinant (denoted by $\Delta$) is $t = a + d$ and $\Delta = ad-bc$ respectively. Then the characteristic polynomial of $A$ is:

\begin{aligned} c_{A}(\lambda) &= \det(\lambda I - A) = \det \begin{pmatrix} \lambda - a & -b \\ -c & \lambda - d \end{pmatrix} \\ &= (\lambda - a)(\lambda - d) - bc \\ &= \lambda^2 - t \lambda + \Delta \end{aligned}

Thus, by the Cayley-Hamilton Theorem:

$A^2 - tA + \Delta = \bf{0}$

or:

$A^2 = tA - \Delta$

What we can see is that $A^2$ can be expressed in terms of $A$, $t$ and $\Delta$. Can we express $A^3$ in terms of $A$, $t$ and $\Delta$? Well, let's compute this:

\begin{aligned} A^3 &= AA^2 = A(tA - \Delta) \\ &= tA^2 - \Delta A = t(tA - \Delta) - \Delta A \\ &= (t^2 - \Delta)A - t\Delta \end{aligned}

So here's two open problems for you:

1) How to express $A^n$ in terms of $A$, $t$ and $\Delta$?

2) Can we do something similar for square matrix of arbitrary sizes? How about a 3 x 3 matrix?

Note by A Former Brilliant Member
3 years, 11 months ago

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

• Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
• Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
• Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold
- bulleted- list
• bulleted
• list
1. numbered2. list
1. numbered
2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in $$ ... $$ or $ ... $ to ensure proper formatting.
2 \times 3 $2 \times 3$
2^{34} $2^{34}$
a_{i-1} $a_{i-1}$
\frac{2}{3} $\frac{2}{3}$
\sqrt{2} $\sqrt{2}$
\sum_{i=1}^3 $\sum_{i=1}^3$
\sin \theta $\sin \theta$
\boxed{123} $\boxed{123}$

Sort by:

For problem 1, here's an outline of an idea that I think might work, though I'm not very sure. Also, I think this method will give the closed form in the form of some cases with conditions imposed on $t$ and $\Delta$.

Denote $x_n=A^n$ and define $A^0=I$ where $I$ is the identity matrix of the same order as $A$. Then we have,

$x_n=A^n=A^2A^{n-2}=(tA-\Delta)A^{n-2}=tA^{n-1}-\Delta A^{n-2}=tx_{n-1}-\Delta x_{n-2}~\forall~n\geq 2\qquad(1)$

Since $t$ and $\Delta$ only depend on $A$ which is independent of $n$, we note that $t,\Delta$ are independent of $n$ and hence $(1)$ can be seen as a linear recurrence relation with constant coefficients and we can use the method described here to get a closed form for $x_n$, i.e., a closed form for $A^n$ in terms of $t,\Delta,A$ using the initial values $x_0=I$ and $x_1=A$.

I tried working on the case where the auxillary equation for the recurrence has distincts non-zero roots, i.e., when $\Delta\neq 0$ and $t^2\neq\Delta$, and let me tell you, the result is not very pretty. We have,

$A^n = c_1\alpha^n + c_2\beta^n$

where $\alpha,\beta=\dfrac{-t\pm\sqrt{t^2-4\Delta}}2$ and $c_1=\dfrac 1{\beta-\alpha}(\beta I-A)$ and $c_2=\dfrac 1{\beta-\alpha}(-\alpha I+A)$

I think there might be a better way to approach the problem but this is all I have right now. Will update the comment if I figure out a better way.

- 3 years, 11 months ago

I guess Problem 1 is almost solved; once you have the linear recurrence, just find the generating function and go from there (I know I'm projecting, and I'm expecting some sort of sh*tstorm!).

Any ideas on Problem 2?

- 3 years, 11 months ago

Essentially yes. What you want is the characteristic polynomial of the matrix which arises from cayley hamilton theorem. Say it has degree $d \leq n$.

Then, every matrix $A^k$ can be expressed as $I, A, A^2, \ldots, a^{d-1}$ by repeated substituting in the characteristic polynomial. You could use the linear recurrence relations to solve for each coefficient if desired.

Staff - 3 years, 11 months ago