The Householder "Rank" of Orthogonal Matrix

Question

Any vector $v\in \mathbb{R}^d$ defines a Householder matrix $H=I-2\frac{vv^T}{v^Tv}\in\mathbb{R}^{d\times d}$.

Any orthogonal matrix $U\in \mathbb{R}^{d\times d}$ can be written as a product $U=H_1\cdots H_d$ of at most $d$ Householder matrices.

Some orthogonal matrices require less Householder matrices, i.e., $U=H_1\cdots H_k$ for $k\ll d$.

Let the "Householder rank" of an orthogonal matrix $U$ be the smallest number $r$ of Householder matrices so $U=H_1\cdots H_{r}$.

Consider singular value decomposition $U\Sigma V^T$ of $D+wv^T$ where $D$ is diagonal and $wv^T$ is an outer product.

Can we prove that $U,V$ has low Householder rank?

Answer 1

I suspect that $U,V$ will not necessarily be of low Householder rank for the following reason:

• A matrix $U$ of low Householder-rank will have $1$ as an eigenvalue with high multiplicity. In particular, we can verify that if $H_i = I - 2v_iv_i^T$ for unit vectors $v_i$, then $U = H_1\cdots H_k$ will satisfy $Uw = w$ for all $w \in \{v_1,\dots,v_k\}^\perp$, so that the eigenvalue $1$ has multiplicity at least $d-k$.

• Finding the SVD of $D = \operatorname{diag}(1,2,\dots,n)$ and $u = v = (1,\dots,1)$ (numerically, with matlab) yields a $U$ that has no repeated eigenvalues.

If you would like to try for yourself in Matlab, here's my code:

N = 20;
[U,~,~] = svd(ones(N) + diag(1:N));
length(unique(eig(U)))        % number of distinct eigenvalues of U
sum(eig(U) == 1)              % multiplicity of eigenvalue 1