LemmaStatement: Literature-sourcedProof: AI-adaptedPipeline-generatedprecheck pass

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 ridge information matrix is positive definite and invertible

Statement

In the finite-dimensional linear contextual bandit model, for every $0 \leq t \leq n$ the matrix $V_{t} = λ I_{d} + \sum_{s = 1}^{t} A_{s} A_{s}^{T}$ is symmetric and satisfies $x^{T} V_{t} x > 0$ for every nonzero $x \in R^{d}$ . It is invertible, has determinant at least $λ^{d} > 0$ , and for every $x \in R^{d}$ ,

$x^{T} V_{t}^{- 1} x \leq \frac{∥ x ∥_{2}^{2}}{λ} .$

Statement references

Tor Lattimore and Csaba Szepesvári, Bandit Algorithms, §19.2

Facts & Assumptions

Given: The model's fixed $λ > 0$ , feature vectors $A_{s} \in R^{d}$ , and the matrices $V_{t} = λ I_{d} + \sum_{s = 1}^{t} A_{s} A_{s}^{T}$ .

[F1]

Finite-dimensional linear contextual bandit model gives the displayed $V_{t}$ and Euclidean feature vectors.

[F2]

The Euclidean inner product $⟨ x, y ⟩ = \sum_{k < n} x_{k} y_{k}$ on $R^{n}$ : $x^{T} y = ⟨ x, y ⟩$ and $∥ x ∥_{2}^{2} = x^{T} x$ .

[F3]

Real spectral theorem: a self-adjoint endomorphism of a finite-dimensional real inner product space has an orthonormal eigenbasis: a real symmetric matrix has an orthonormal eigenbasis.

[F4]

Hermitian positive-definite matrices and Cholesky factorisation A = LL* with positive diagonal and A matrix admits a Cholesky factorisation with positive diagonal exactly when it is Hermitian positive definite, and that factor is unique: a real symmetric matrix with positive quadratic form on nonzero vectors factors as $L L^{T}$ with positive diagonal.

[F5]

For $n \geq 1$ , the determinant over a commutative ring by the Leibniz formula, and $∣ \det A ∣$ for a real matrix, For same-sized finite square matrices over a commutative ring, $\det (A B) = \det (A) \det (B)$ , For every square matrix over a commutative ring, $\det (A^{T}) = \det (A)$ , and The determinant of a triangular matrix is the product of its diagonal entries: determinant is multiplicative and unchanged by transpose; for triangular $L$ it is the product of its diagonal entries. Thus for an orthogonal $Q$ , $\det (Q) \det (Q^{T}) = \det (Q Q^{T}) = 1$ .

[F6]

A finite square real matrix is invertible if and only if its determinant is nonzero: a real square matrix with nonzero determinant is invertible.

Proof

1.1givenF1F2algebra

For any $x \neq 0$ , the model formula gives $x^{T} V_{t} x = λ ∥ x ∥_{2}^{2} + \sum_{s = 1}^{t} (A_{s}^{T} x)^{2} > 0,$ since $λ > 0$ and $∥ x ∥_{2} > 0$ . Each summand $A_{s} A_{s}^{T}$ is symmetric, so $V_{t}$ is symmetric as well.

2.1step 1.1F3algebrachoose

By [F3], choose an orthonormal eigenbasis $q_{1}, \dots, q_{d}$ of $V_{t}$ with eigenvalues $μ_{1}, \dots, μ_{d}$ . Applying step 1.1 to each unit eigenvector gives $μ_{i} = q_{i}^{T} V_{t} q_{i} \geq λ$ .

2.2step 1.1F4F5F6algebra

Alternatively identifying the determinant sign explicitly, [F4] gives $V_{t} = L L^{T}$ with positive diagonal. By [F5], $\det V_{t} = (\prod_{i} L_{i i})^{2} > 0$ ; [F6] therefore also yields invertibility.

3.1step 2.1F2algebra

Expand any $x = \sum_{i} c_{i} q_{i}$ in that orthonormal basis. Then $x^{T} V_{t}^{- 1} x = \sum_{i} c_{i}^{2} / μ_{i} \leq λ^{- 1} \sum_{i} c_{i}^{2} = λ^{- 1} ∥ x ∥_{2}^{2}$ , using $μ_{i} \geq λ > 0$ . This also shows $V_{t}^{- 1}$ exists.

3.2step 2.1F3F5algebra

The same diagonalization and [F5] give $\det V_{t} = \det (Q) \det (diag (μ_{1}, \dots, μ_{d})) \det (Q^{T}) = \prod_{i} μ_{i} \geq λ^{d} > 0$ .

4.1step 1.1step 2.2step 3.1step 3.2given∎

Steps 1.1, 2.2, 3.1, and 3.2 prove symmetry, strict positivity of the quadratic form, the inverse bound, the determinant lower bound, and invertibility for each $t$ . The case $t = 0$ uses the same formulas with an empty sum.

Depends on

Used by

Dependency tree · two levels

59 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

Tor Lattimore and Csaba Szepesvári, Bandit Algorithms (standard reference, not scraped)