Hankel realization recovers a controllable and observable system

If $d=0$, then $B$ has no rows and $C$ has no columns, so $M_k=0$ for every $k$ and $H_0=H_1=0$. Its rank is zero, and the algorithm's exact empty factorization and empty pseudoinverses return the unique empty matrices. Taking $T=I_0$ gives the asserted similarity. Henceforth suppose $d\ge 1$.

For $0\le i,j<q$, the $(i,j)$ block of $H_0$ is $M_{i+j}=C{A}^{i+j}B=(C{A}^i)(A^{j}B)$ by [F1] and [F2], and the corresponding block of $H_1$ is $M_{i+j+1}=(C{A}^i)A(A^{j}B)$. Thus $H_0=O_q{R}_q$ and $H_1=O_{q}A{R}_q$. Because $R_q$ has rank $d$ and codomain ${\mathbb{R}}^d$, it is surjective; because $O_q$ has rank $d$ and domain ${\mathbb{R}}^d$, it is injective. Therefore $\mathrm{im}{H}_0=\mathrm{im}{O}_q$ and $\mathrm{rank}{H}_0=d$.

The exact rank test in the algorithm therefore returns $d$. The SVD factorization and pseudoinverses exist by [F6], and the stated successful-call hypothesis ensures that the algorithm returns factors $H_0=\widehat{O}\widehat{R}$ with each factor of rank $d$ and returns success. In particular $\widehat{R}$ is surjective, so $\mathrm{im}{H}_0=\mathrm{im}\widehat{O}$. Combining this with step 1.2 gives $\mathrm{im}\widehat{O}=\mathrm{im}{O}_q$.

The columns of $O_q$ and $\widehat{O}$ are bases of the same $d$-dimensional image by step 2.1. Thus there is a unique $d\times d$ matrix $T$ with $\widehat{O}=O_{q}T$. If $Tv=0$, then $\widehat{O}v=O_{q}Tv=0$; since $\widehat{O}$ has rank $d$, its kernel is zero, so $v=0$. Rank-nullity [F3] and [F4] makes the square matrix $T$ surjective as well as injective; hence $T$ is invertible by [F8]. From $O_q{R}_q=H_0=O_{q}T\widehat{R}$ and injectivity of $O_q$, $R_q=T\widehat{R}$, so $\widehat{R}=T^{-1}{R}_q$.

Substituting $O_q=\widehat{O}{T}^{-1}$ and $R_q=T\widehat{R}$ into the identity in step 1.2 gives $H_1=\widehat{O}(T^{-1}AT)\widehat{R}$. Since $\widehat{O}$ has full column rank, ${\widehat{O}}^{+}\widehat{O}=I_d$: the equation $\widehat{O}{\widehat{O}}^{+}\widehat{O}=\widehat{O}$ from [F7] and injectivity imply this identity. Since $\widehat{R}$ has full row rank, $\widehat{R}{\widehat{R}}^{+}=I_d$: [F7] gives $\widehat{R}{\widehat{R}}^{+}\widehat{R}=\widehat{R}$, and surjectivity implies the identity. The algorithm's formula then yields $\widehat{A}={\widehat{O}}^{+}{H}_1{\widehat{R}}^{+}=T^{-1}AT$.

The first $m$ columns of $R_q$ form $B$, and the first $p$ rows of $O_q$ form $C$. Taking those blocks in $\widehat{R}=T^{-1}{R}_q$ and $\widehat{O}=O_{q}T$ gives $\widehat{B}=T^{-1}B$ and $\widehat{C}=CT$. Hence the triple returned by the algorithm satisfies all three similarity identities.

By [F9], the similarity identities imply identical outputs for every finite common-input experiment when initial states are related by $T^{-1}$. With zero initial state and an impulse input, this gives $\widehat{C}{\widehat{A}}^k\widehat{B}=C{A}^{k}B$ for every $k\ge 0$. This is exact realization modulo state similarity; it asserts no stability under perturbed Markov data.