DefinitionDefinition: Literature-sourcedProof: Not applicablejudge 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.

The row-shift companion matrix of a linear recurrence

Definition

Let $R$ be a commutative ring, let $d \geq 1$ , and let

$χ (t) = t^{d} + c_{1} t^{d - 1} + \dots + c_{d} .$

The row-shift companion matrix of this recurrence polynomial is the matrix $C \in M_{d} (R)$ (Finite rectangular matrices over a commutative ring, their entries, rows and columns) whose entries are

$C_{i, i + 1} = 1 (0 \leq i < d - 1), C_{d - 1, j} = - c_{d - j} (0 \leq j < d),$

with all other entries zero. Thus

$C = (\begin{array}{ccccc} 0 & 1 & 0 & \dots & 0 \\ 0 & 0 & 1 & \dots & 0 \\ ⋮ & ⋱ & ⋮ \\ 0 & 0 & 0 & \dots & 1 \\ - c_{d} & - c_{d - 1} & - c_{d - 2} & \dots & - c_{1} \end{array}) .$

For a recurrence sequence $a$ , its state at time $n$ is the column vector $v_{n} = (a_{n}, a_{n + 1}, \dots, a_{n + d - 1})^{T}$ . This convention matches the signs and order in Constant-coefficient linear recurrences, their starting index and their characteristic polynomial.

Depends on

Used by

Dependency tree · two levels

7 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, slides 16-18 (standard reference, not scraped)