# determining orthonormal matrix of rank N with special first row

Is there a more efficient algorithm besides Gram-Schmidt that would produce an orthonormal matrix of rank N, with first row equal to [1 1 1 1 1 ... 1] / sqrt(N)?

e.g. for N = 3, the matrix \begin{align} \mathsf A_3 &= \begin{bmatrix} 1/\sqrt 3 & 1/\sqrt 3 & 1/\sqrt 3 \\ 2/\sqrt 6 & -1/\sqrt 6 & -1/\sqrt 6 \\ 0 & 1/\sqrt 2 & -1/\sqrt 2 \end{bmatrix}\end{align} suffices, but I'm not sure how to generalize.

-
please help me with my math latex, I tried adapting from other posts but can't seem to get the matrix rows to show up. –  Jason S Oct 18 '10 at 14:05
ah-- thanks! so you have to escape the \\\\ symbols. –  Jason S Oct 18 '10 at 14:10
If you'd settle for unitary matrices, you could use a Fourier matrix! –  Mariano Suárez-Alvarez Oct 18 '10 at 14:29
yeah, I had thought of that (see my answer) unfortunately I'm looking for real-valued matrices. –  Jason S Oct 18 '10 at 17:40

There's a reflection swapping $v=(\sqrt{n},0,\ldots,0)$ with $w=(1,1,\ldots,1)$ which will do what you want. It will fix $v+w$ and all vectors orthogonal to $v$ and $w$. It will negate $v-w$. It will be a symmetric matrix; its first row and column is all $1/\sqrt{n}$. The remaining entries $a_{i,j}$ for $i$, $j\ge2$ will depend only on whether $i=j$ or not. This should be enough information to reconstruct it.

-
+1, thanks. (p.s. this isn't meant as a criticism, but I am amused by the difference between programmer + mathematician mindsets: "solved" in math circles seems to be proof of existence, "solved" in programmer circles is a description of an algorithm) –  Jason S Oct 18 '10 at 15:02
I'm familiar w/ Householder reflections: is there an easy way to get the normal vector n from the two vectors "v" and "w" as you described? –  Jason S Oct 18 '10 at 15:04
As I said, the vector that gets negated is $v-w$. –  Robin Chapman Oct 18 '10 at 17:53
ah -- great, thanks, I didn't pick up on that one. –  Jason S Oct 18 '10 at 20:52
Hmmm. I don't follow why "its first row and column is all 1/sqrt(n)" is consistent with it being a reflection swapping v and w. –  Jason S Oct 18 '10 at 20:59

Given the special form, you can probably construct a rotation matrix that would turn one of the standard basis vectors there.

-
oh, that makes sense. Any further suggestions how to do that? –  Jason S Oct 18 '10 at 14:09
haven't you just rephrased the question? –  Mariano Suárez-Alvarez Oct 18 '10 at 14:30

You should be able to use K-1 rows of Normalized Hadamard matrices of size K, where K is a power of 2 as building blocks. (How to normalize see this: http://math.stackexchange.com/questions/4797/what-is-sum-of-rows-of-hadamard-matrix/4798#4798) You should be able to construct these rows recursively as K is a power of 2.

Something like

[1 1 ..       1 ]
[ H_1 | 0  |0 0 ]
[ 0   | H_2|0 0 ]
[ 0   | 0  | H_4]


etc

At the end O(LogN) rows will remain to be filled, which I suppose you can use Gram-Schmidt on.

-

hmm, I think one possibility for orthonormal vectors for N odd is

[ 1 1 1 1 1 ... 1 ]
[ 1, cos phi, cos 2*phi, cos 3*phi, ... cos (N-1)*phi ]
[ 0, sin phi, sin 2*phi, sin 3*phi, ... sin (N-1)*phi ]
[ 1, cos 2*phi, cos 4*phi, cos 6*phi, ... cos 2*(N-1)*phi ]
[ 0, sin 2*phi, sin 4*phi, sin 6*phi, ... sin 2*(N-1)*phi ]
...
[ 1, cos k*phi, cos 2*k*phi, cos 3*k*phi, ... cos k*(N-1)*phi ]
[ 0, sin k*phi, sin 2*k*phi, sin 3*k*phi, ... sin k*(N-1)*phi ]


where k = (N-1)/2

but I'm not sure how to extend to N even.

-

I took @Robin Chapman's answer and ran with it:

The matrix A that is the Householder reflection of v-w where v = [sqrt(N), 0, 0, 0, ... ] and w = [1 1 1 1 1 ... 1] can be defined by:

A(1,i) = A(i,1) = 1/sqrt(N)
A(i,i) = 1 - K   for i >= 2
A(i,j) = -K      for i,j >= 2, i != j
K = 1/sqrt(N)/(sqrt(N)-1)

-

Take the transpose of this pattern $$\left( \begin{array}{rrrrrrrrrr} 1 & -1 & -1 & -1 & -1 & -1 & -1 & -1 & -1 & -1 \\ 1 & 1 & -1 & -1 & -1 & -1 & -1 & -1 & -1 & -1 \\ 1 & 0 & 2 & -1 & -1 & -1 & -1 & -1 & -1 & -1 \\ 1 & 0 & 0 & 3 & -1 & -1 & -1 & -1 & -1 & -1 \\ 1 & 0 & 0 & 0 & 4 & -1 & -1 & -1 & -1 & -1 \\ 1 & 0 & 0 & 0 & 0 & 5 & -1 & -1 & -1 & -1 \\ 1 & 0 & 0 & 0 & 0 & 0 & 6 & -1 & -1 & -1 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 & 7 & -1 & -1 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 8 & -1 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 9 \end{array} \right).$$ and divide what will now be the rows by a suitable square root, different for each row.

Here is the transpose that you want, $$\left( \begin{array}{rrrrrrrrrr} 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ -1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ -1 & -1 & 2 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ -1 & -1 & -1 & 3 & 0 & 0 & 0 & 0 & 0 & 0 \\ -1 & -1 & -1 & -1 & 4 & 0 & 0 & 0 & 0 & 0 \\ -1 & -1 & -1 & -1 & -1 & 5 & 0 & 0 & 0 & 0 \\ -1 & -1 & -1 & -1 & -1 & -1 & 6 & 0 & 0 & 0 \\ -1 & -1 & -1 & -1 & -1 & -1 & -1 & 7 & 0 & 0 \\ -1 & -1 & -1 & -1 & -1 & -1 & -1 & -1 & 8 & 0 \\ -1 & -1 & -1 & -1 & -1 & -1 & -1 & -1 & -1 & 9 \end{array} \right).$$

That worked.

For row 1, divide by $\sqrt n.$ For row $i$ with $2 \leq i \leq n,$ divide by $\sqrt{i^2 - i},$ which is double a triangular number. Note that the diagonal entry in row $i$ is $i-1,$ just one of those things. So, except for the first row, if you call the diagonal entry $d,$ divide by $\sqrt{d^2 + d}.$ Which works out the same.

-