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