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.
On
Given the special form, you can probably construct a rotation matrix that would turn one of the standard basis vectors there.
On
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.
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.
On
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)
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.