Waste less time on Facebook — follow Brilliant.

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{split} 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{split} \)

Thus, by the Cayley-Hamilton Theorem:

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


\( 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{split} A^3 &= AA^2 = A(tA - \Delta) \\ &= tA^2 - \Delta A = t(tA - \Delta) - \Delta A \\ &= (t^2 - \Delta)A - t\Delta \end{split} \)

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 Gennady Notowidigdo
11 months, 2 weeks ago

No vote yet
1 vote


Sort by:

Top Newest

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.

Prasun Biswas - 11 months, 2 weeks ago

Log in to reply

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?

Gennady Notowidigdo - 11 months, 2 weeks ago

Log in to reply

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.

Calvin Lin Staff - 11 months, 1 week ago

Log in to reply


Problem Loading...

Note Loading...

Set Loading...