LemmaStatement: 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.

An unreduced Hessenberg similarity is determined up to column phases by its first unitary column

Statement

Let $n \geq 1$ , let $H \in C^{n \times n}$ be upper Hessenberg with every first-subdiagonal entry nonzero. Suppose $Q, V$ are unitary, $Q e_{1} = V e_{1}$ , and both $Q^{*} H Q$ and $V^{*} H V$ are unreduced upper Hessenberg. Then $V^{*} Q$ is diagonal unitary with first diagonal entry $1$ . Thus the two unitary transformations differ only by column phases. Over $R$ the phases are signs.

Facts & Assumptions

Given: $H, Q, V$ as in the statement.

[F1]

Upper Hessenberg matrices and real symmetric tridiagonal matrices: upper Hessenberg means entries below the first subdiagonal vanish. The nonzero subdiagonal entries are the explicit unreduced hypothesis in the statement.

[F2]

Linear isometries, and orthogonal or unitary operators on finite-dimensional inner product spaces: $Q$ and $V$ are unitary, so $W = V^{*} Q$ is unitary.

Proof

1.1givenF2algebra

Put $G = V^{*} H V$ , $F = Q^{*} H Q$ , and $W = V^{*} Q$ . Then $G W = W F$ and $W e_{1} = e_{1}$ by direct multiplication and $Q e_{1} = V e_{1}$ .

2.1F1step 1.1algebra

Write $w_{j}$ for column $j$ of $W$ . We prove by induction that $w_{j}$ is supported in its first $j$ coordinates. This holds for $j = 1$ by step 1.1. If it holds through $j$ , the $j$ th column of $G W = W F$ gives $G w_{j} = \sum_{i = 1}^{j + 1} f_{i j} w_{i}$ . The vector $G w_{j}$ is supported in rows $1, \dots, j + 1$ because $G$ is upper Hessenberg, and $w_{1}, \dots, w_{j}$ are supported in their first $j$ coordinates. Since $f_{j + 1, j} \neq 0$ by unreducedness of $F$ , solving this equality for $w_{j + 1}$ shows it is supported in rows $1, \dots, j + 1$ .

3.1F2step 2.1algebra∎

Step 2.1 makes $W$ upper triangular. An upper-triangular unitary matrix is diagonal: its first column has only one nonzero entry of modulus one, orthogonality makes the rest of its first row zero, and induction applies to the trailing principal block. Since $W e_{1} = e_{1}$ , the first diagonal entry is $1$ .

Depends on

Used by

Under unreduced hypotheses, the Francis double-shift chase matches explicit shifted QR Lemma

Dependency tree · two levels

6 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

James Demmel, Math 221 Lecture 16: The implicit Q theorem (standard reference, not scraped)
David Bindel, CS 6210 Matrix Computations, Hessenberg QR iteration (standard reference, not scraped)