THE GARDEN

Cayley-Hamilton Reduction of Matrix Exponentiation to Polynomial Coefficients

Updated 13 Sep 2026

• •

  What it is

  • •

    Cayley–Hamilton reduces every matrix power to a polynomial in lower powers. If w=G^s*v is known, solve the linear system with columns v, Gv, … to recover its coefficients when that Krylov matrix has full rank. A rank-deficient observation may identify only the action on a smaller subspace.

• •

  When to apply

  • •

    A scheme reveals $w=G^sv$ for a known base matrix $G$ and known vector $v$, with the exponent $s$ itself unknown — regardless of whether $s$ is later recovered via a repeated-eigenvalue shortcut or a full discrete log, this reduction step is the common first move for "RSA/DH but with matrix exponents" challenges.

• •

  Symbols and assumptions

  • •

    G is an n×n matrix over a field, v a known column vector, and $w=G^sv$. Write $f(X)=\det(XI-G)$; the minimal polynomial may give an even smaller reduction.

• •

  Math — step by step

  • •
    1. Cayley–Hamilton gives $f(G)=0$. Divide $X^s$ by f: $X^s=q(X)f(X)+a(X)$, with degree a<n. Substituting G cancels the multiple of f and leaves $G^s=a(G)$.
  • •
    2. Therefore $w=a_0v+a_1Gv+\cdots+a_{n-1}G^{n-1}v$. Build the Krylov matrix $K=[v\ Gv\ \cdots\ G^{n-1}v]$ and solve $Ka=w$.
  • •
    3. The coefficients are uniquely recovered this way only if K has full column rank. If K is singular, a solution reproducing w may differ from the actual remainder modulo f. Work in the smaller cyclic subspace or obtain additional observations before using derivatives or field projections.
• •

  Worked example

  • •

    Over $GF(5)$ take $G=\begin{pmatrix}1&1\\0&1\end{pmatrix}$ and $v=(0,1)^T$. Here $f=(X-1)^2=X^2-2X+1$, so $G^2=2G-I$.

  • •

    Reduce $X^3$: $X^3=2X^2-X\equiv2(2X-1)-X=3X-2=3X+3\pmod{5,f}$. Thus $G^3=3I+3G$.

  • •

    Compute $Gv=(1,1)^T$ and $w=G^3v=(3,1)^T$. Solve $\begin{pmatrix}0&1\\1&1\end{pmatrix}(a_0,a_1)^T=(3,1)^T$: $a_1=3$ and $a_0=1-3\equiv3$. These are exactly the remainder coefficients.

• •

  Python

  • •

    cols = []
    Gi = identity(n)
    for i in range(n):
            cols.append(mat_vec(Gi, v))
            Gi = mat_mul(Gi, G)
    K = [[cols[j][i] for j in range(n)] for i in range(n)]   # K's columns are G^i v
    a_coeffs = gauss_solve(K, w)   # solve K @ a = w
    

• •

  SageMath

  • •

    K = Matrix(F, [G**i * v for i in range(n)]).transpose()
    a_coeffs = K.solve_right(w)
    f = G.charpoly()   # the reduction modulus, if needed further
    

• •

  Related

  • •

    Matrix Groups & Textbook-RSA-Style Attacks over Matrices

  • •

    Chinese Remainder Theorem

• •

  Cards

  • •

    What does the Cayley-Hamilton theorem guarantee that makes this reduction possible?

    • •

      Every square matrix satisfies its own characteristic polynomial, so any power of the matrix can be re-expressed using only powers up to one less than its dimension

  • •

    Why can the polynomial coefficients be recovered without knowing the secret exponent s?

    • •

      The relationship is linear in the coefficients. Full column rank of [v, Gv, …] is required for unique coefficient recovery from that observation.

◌ Explore connections in Graph view