Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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
2  
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

6 Answers 6

up vote 7 down vote accepted

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.

share|improve this answer
    
+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

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.

share|improve this answer

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)
share|improve this answer

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.

share|improve this answer

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.

share|improve this answer

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

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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.