3
$\begingroup$

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.

  • 0
    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.2010-10-18
  • 0
    ah-- thanks! so you have to escape the \\\\ symbols.2010-10-18
  • 2
    If you'd settle for unitary matrices, you could use a Fourier matrix!2010-10-18
  • 0
    yeah, I had thought of that (see my answer) unfortunately I'm looking for real-valued matrices.2010-10-18

6 Answers 6

7

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.

  • 0
    +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)2010-10-18
  • 0
    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?2010-10-18
  • 0
    As I said, the vector that gets negated is $v-w$.2010-10-18
  • 0
    ah -- great, thanks, I didn't pick up on that one.2010-10-18
  • 0
    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.2010-10-18
1

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

  • 0
    oh, that makes sense. Any further suggestions how to do that?2010-10-18
  • 1
    haven't you just rephrased the question?2010-10-18
1

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: What is sum of rows of Hadamard matrix) 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.

1

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)
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.

EDIT, MAY 2016: user1551 found this in a particular book, here is the version in their solutions manual, page 97, talking about Exercise 4.24:

enter image description here

  • 1
    **Remark.** Incidentally, this "Jagy matrix" also appears in exercise 4.24 of Härdle *et al.* (2014), *Basics of Modern Mathematical Statistics*.2016-05-31
  • 0
    @user1551 thanks. Quite a regular thing on this site, orthogonal basis of eigenvectors for the matrix with all entries equal to $1,$ or that matrix plus a multiple of $I.$ . Found it, maybe the solutions manual: https://books.google.com/books?id=Wkq3BAAAQBAJ&pg=PA97&lpg=PA97&dq=Basics+of+Modern+Mathematical+Statistics+Hardle+4.24&source=bl&ots=x3Tc2uvAfT&sig=n-a3yG4uNjswd9cmDYm50cDPbRE&hl=en&sa=X&ved=0ahUKEwinvqGI64TNAhVC82MKHUSoC2QQ6AEIMTAD#v=onepage&q=Basics%20of%20Modern%20Mathematical%20Statistics%20Hardle%204.24&f=false2016-05-31
0

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.