CorollaryStatement: AI-adaptedProof: AI-adaptedprecheck passjudge pass (deepseek-v4-pro + gpt-5.6-terra)audited 2026-08-16

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

For an invertible matrix over a field, Cayley-Hamilton makes every matrix-power entry and trace sequence linearly recurrent

Statement

Let $K$ be a field, let $n \geq 1$ , and let $A \in M_{n} (K)$ be invertible. Write

$χ_{A} (t) = t^{n} + b_{1} t^{n - 1} + \dots + b_{n} .$

Then $b_{n} \neq 0$ , and for every pair $u, v < n$ the sequence $m \mapsto (A^{m})_{u v}$ , as well as the sequence $m \mapsto tr (A^{m})$ , satisfies from $m = 0$ the order- $n$ recurrence

$s_{m + n} + b_{1} s_{m + n - 1} + \dots + b_{n} s_{m} = 0.$

Facts & Assumptions

Given: A field $K$ , a positive size $n$ , and an invertible matrix $A \in M_{n} (K)$ with the displayed characteristic polynomial.

[L1]

Every finite-dimensional endomorphism satisfies its characteristic polynomial: $χ_{T} (T) = 0$ (Cayley-Hamilton: every finite-dimensional endomorphism satisfies its characteristic polynomial, $χ_{T} (T) = 0$ ).

[L2]

A matrix $A$ defines the coordinate endomorphism $T_{A} (x) = A x$ (For $A \in M_{n} (R)$ , the coordinate endomorphism $T_{A} : R^{n} \to R^{n}$ , with $\det (T_{A}) : = \det (A)$ and $adj (T_{A}) : = T_{adj (A)}$ ).

[L3]

The operator characteristic polynomial is the characteristic polynomial of any representing matrix (The basis-independent characteristic polynomial $χ_{T}$ of an endomorphism of a finite-dimensional space, including $χ_{T} = 1$ in dimension zero).

[L4]

The matrix characteristic polynomial is $χ_{A} (t) = \det (t I - A)$ (For $A \in M_{n} (F)$ , the characteristic polynomial is $χ_{A} (x) = \det (x I_{n} - A)$ when $n \geq 1$ , with $χ_{A} (x) = 1$ for the unique $0 \times 0$ matrix).

[L5]

The trace of a field matrix is the finite sum of its diagonal entries (The trace $tr (A)$ as the sum of the diagonal entries).

[L6]

An invertible positive-sized matrix over a commutative ring has unit determinant (An invertible square matrix over a commutative ring has unit determinant).

Proof

technique · direct

1.1givenL1L2L3

Apply [L1] to the coordinate endomorphism [L2]. By [L3], its characteristic polynomial is $χ_{A}$ , so the representing matrices satisfy $A^{n} + b_{1} A^{n - 1} + \dots + b_{n} I = 0$ .

1.2L4L6algebra

By [L4], the constant coefficient is $b_{n} = \det (- A) = (- 1)^{n} \det (A)$ . The determinant is a unit by [L6], so $b_{n} \neq 0$ in the field $K$ and the relation has order $n$ under the page's recurrence convention.

2.1step 1.1algebra

Multiplying the identity in step 1.1 by $A^{m}$ gives $A^{m + n} + b_{1} A^{m + n - 1} + \dots + b_{n} A^{m} = 0$ for every $m \geq 0$ .

3.1step 2.1L5algebra

Extracting the $(u, v)$ entry from step 2.1 proves the displayed recurrence for every matrix-power entry; summing its diagonal entries and using [L5] proves the same recurrence for the trace sequence.

4.1step 3.1step 1.2∎

Steps 3.1 and 1.2 establish both families of order- $n$ recurrences from $m = 0$ .

Depends on

Used by

Cyclic monomer–domino tilings are counted by Lucas numbers through a matrix trace Example

Dependency tree · two levels

27 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources

M. Waldschmidt, Linear Recurrence Sequences VI, slide 18 (standard reference, not scraped)