TheoremStatement: Literature-sourcedProof: AI-adaptedPipeline-generated

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.

HiPPO LegS, LegT, and LagT matrices have normal-plus-low-rank form after specified similarities

Statement

Index rows and columns by $0, \dots, N - 1$ . Define the real LegS coefficient matrix $G^{S}$ by $G_{n k}^{S} = - \sqrt{(2 n + 1) (2 k + 1)}$ when $n > k$ , $G_{n n}^{S} = - (n + 1)$ , and $G_{n k}^{S} = 0$ when $n < k$ . In the LegS coefficient ODE for $t > 0$ this matrix is multiplied by the time-dependent scalar $1 / t$ ; the matrix assertion below does not make that ODE time-invariant. For $θ > 0$ , define the LegT state generator by $G_{n k}^{T} = - (2 n + 1) (- 1)^{n - k} / θ$ when $n \geq k$ and $G_{n k}^{T} = - (2 n + 1) / θ$ when $n < k$ . Define the original HiPPO LagT state generator by $G_{n k}^{L} = - 1$ when $n \geq k$ and $G_{n k}^{L} = 0$ when $n < k$ . Here $X^{*}$ is conjugate transpose, a complex matrix $H$ is normal when $H^{*} H = H H^{*}$ , and a square matrix $V$ is unitary when $V^{*} V = V V^{*} = I$ . For LegS and LagT use the identity similarity; for LegT use the invertible diagonal similarity $S_{0} = diag (\sqrt{2 n + 1})_{n = 0}^{N - 1} diag ((- 1)^{n})_{n = 0}^{N - 1}$ . Each transformed matrix is a difference $H - U V^{*}$ with $H$ normal and $rank (U V^{*}) \leq 1$ for LegS and LagT and $rank (U V^{*}) \leq 2$ for LegT. Consequently the equivalent finite-dimensional complex state-space matrix has a normal-plus-low-rank representation, and a unitary change of state coordinates gives diagonal-plus-low-rank form. Under any state change $x = S \tilde{x}$ , the input and output vectors change to $S^{- 1} B$ and $S^{*} C$ , respectively.

Statement references

Gu, Goel, and Ré, “Efficiently Modeling Long Sequences with Structured State Spaces,” Theorem 1 and Appendix C.1

Gu et al., “HiPPO: Recurrent Memory with Optimal Polynomial Projections,” §2.3 and Appendices D.1–D.3

Facts & Assumptions

Given: The finite matrices in the Statement, the parameter $θ > 0$ for LegT, and finite-dimensional complex state coordinates.

[F1]

DPLR structured state-space parameterization: a normal-plus-low-rank matrix has form $A = V Λ V^{*} - P Q^{*}$ with unitary $V$ and diagonal $Λ$ ; under the state change $\tilde{x} = V^{*} x$ , the input and output vectors become $V^{*} B$ and $V^{*} C$ .

[F2]

Complex spectral theorem: a normal endomorphism of a finite-dimensional complex inner product space has an orthonormal eigenbasis, and conversely: every normal endomorphism of a finite-dimensional complex inner product space has an orthonormal basis of eigenvectors.

Proof

1.1F1algebra

Put $w_{n} = \sqrt{2 n + 1}$ and define the real skew-symmetric matrix $S$ by $S_{n k} = - w_{n} w_{k} / 2$ for $n > k$ , $S_{n k} = w_{n} w_{k} / 2$ for $n < k$ , and $S_{n n} = 0$ . The transpose is $- S$ , so over $C$ its conjugate transpose is also $- S$ ; hence $S$ is normal. With $v = w / \sqrt{2}$ , entrywise comparison gives $G^{S} = (S - \frac{1}{2} I) - v v^{*}$ : below the diagonal the entries are $- w_{n} w_{k}$ , above they cancel to zero, and on the diagonal they are $- \frac{1}{2} - (2 n + 1) / 2 = - (n + 1)$ . Since a scalar shift of a normal matrix is normal and $v v^{*}$ has rank at most one, this is the required LegS decomposition. This assertion concerns the finite coefficient matrix only; the factor $1 / t$ in the LegS ODE remains time-dependent.

1.2F1algebra

Define $S$ with entries $- 1 / 2$ below the diagonal, $+ 1 / 2$ above it, and zero on the diagonal. It is real skew-symmetric and therefore normal. For $e = (1, \dots, 1)^{T}$ , entrywise comparison gives $G^{L} = (S - \frac{1}{2} I) - \frac{1}{2} e e^{*}$ : below the diagonal the two terms sum to $- 1$ , above they sum to zero, and on the diagonal they sum to $- 1$ . Thus the original LagT generator is a normal matrix minus a rank-at-most-one matrix.

1.3F1algebra

For LegT let $D = diag (2 n + 1)_{n = 0}^{N - 1}$ and $E = diag ((- 1)^{n})_{n = 0}^{N - 1}$ . Define $T_{n k} = 1$ for $n \geq k$ , and $T_{n k} = (- 1)^{k - n}$ for $n < k$ . Then direct entry evaluation gives $G^{T} = - D E T E / θ$ : for $n \geq k$ , $(- 1)^{n} (- 1)^{k} = (- 1)^{n - k}$ , while for $n < k$ , $(- 1)^{n} (- 1)^{k - n} (- 1)^{k} = 1$ . Write $T = S + R$ , where $R_{n k} = 1$ when $n$ and $k$ have the same parity and is zero otherwise. The matrix $R$ is the sum of the outer products of the even-index and odd-index indicator vectors, so its rank is at most two. For opposite parities, $S_{n k} = 1$ below the diagonal and $S_{n k} = - 1$ above it; for equal parities and on the diagonal, $S_{n k} = 0$ . Thus $S^{T} = - S$ . The invertible diagonal matrix $S_{0} = D^{1 / 2} E$ gives $S_{0}^{- 1} G^{T} S_{0} = - θ^{- 1} D^{1 / 2} S D^{1 / 2} - θ^{- 1} D^{1 / 2} R D^{1 / 2}$ . The first term is real skew-symmetric and hence normal; the second has rank at most two. The diagonal similarity is essential: this proves the claim for an equivalent state-space matrix, not unitary similarity of the raw LegT matrix.

2.1F1F2step 1.1step 1.2step 1.3algebra∎

In each case write the resulting generator as $H - U V^{*}$ with $H$ normal: for LegS and LagT the factors are the displayed real vectors divided by $\sqrt{2}$ , and for LegT use the even and odd indicator columns multiplied by $D^{1 / 2} / \sqrt{θ}$ as both factors. By [F2], choose a unitary matrix $V_{0}$ with $V_{0}^{*} H V_{0} = Λ$ diagonal. Then $V_{0}^{*} (H - U V^{*}) V_{0} = Λ - (V_{0}^{*} U) (V_{0}^{*} V)^{*}$ , preserving the low-rank bound. If the original coordinates were changed by $S_{0}$ , the total state change is $x = S_{0} V_{0} z$ ; substitution into $x^{'} = G x + B u$ , $y = C^{*} x$ gives $z^{'} = (V_{0}^{*} S_{0}^{- 1} G S_{0} V_{0}) z + V_{0}^{*} S_{0}^{- 1} B u$ and output vector $V_{0}^{*} S_{0}^{*} C$ . These are exactly the state-coordinate transformations required for an equivalent DPLR model.

Depends on

Used by

S4 convolution-filter arithmetic and numerical cost Theorem

Dependency tree · two levels

8 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

Gu, Goel, and Ré, Efficiently Modeling Long Sequences with Structured State Spaces, Theorem 1 and Appendix C.1 (standard reference, not scraped)
Gu et al., HiPPO: Recurrent Memory with Optimal Polynomial Projections, §2.3 and Appendices D.1–D.3 (standard reference, not scraped)