Sparse orthogonal matrices. (Q1414141)

The sparsity of orthogonal matrices which have both a column and a row of nonzero is studied. In Section 2, the authors describe a rich family \(n\) by \(n\) orthogonal matrices, namely, those that are the product of \(n-1\) Givens rotations. They show that this family contains a sparsest fully indecomposable orthogonal matrix with a full row. They also show that the smallest number of nonzero entries in a matrix which is in this family and which has both a full row and a full column is \((n^2+ 3n-2)/2\). In Section 3, for \(n\geq 6\) they construct \(n\) by \(n\) orthogonal matrices with both a full row and column that have \[ g(n):= \begin{cases} (2k+2)n- 7\cdot 2^{k-1}+ 3\quad &\text{if }2^k\leq n\leq 2^k+ 2^{k-1},\\ (2k+ 3)n- 10\cdot 2^{k-1}+ 3\quad &\text{if }2^k+ 2^{k-1}< n< 2^{k+1}\end{cases} \] nonzero entries, which is significantly smaller than the sparsity, \((n^2+ 3n- 2)/2\), for such an orthogonal matrix that is the product of \(n-1\) Givens rotations.