A puzzle on orthogonal matrices modulo $p$ I'm interested in orthogonal matrices over the ring $\def\Z{\mathbb Z}\def\F{\mathbb F}\F_p := \Z/p\Z$. Here, I mean orthogonal with respect to the usual dot-product: an $n \times n$ matrix $M$ is orthogonal if $M^{\;\!\!\mathsf T\!} M = I$, or equivalently if
$$ (M\mathbf x)\cdot(M\mathbf y) = \mathbf x \cdot \mathbf y$$
for all vectors $\mathbf x,\mathbf y \in \F_p^n$. I'm engaged in a technical bit of research involving such matrices, which — I suspect — may not require any more heavy machinery than results regarding quadratic residues, and perhaps counting arguments.
Question.
For $p$ any prime, is there a $4 \times 4$ matrix $M$ which is orthogonal modulo $p$, such that $M_{1,1} = M_{2,1} = 1$? 
 A: What you're asking for is an example of an orthogonal design [1, 2] evaluated modulo $p$; the same construction will work for any modulus $N \geqslant 1$ and any value for the 2-norm.
Take any unit vector $\mathbf v = (a,b,c,d)$. We associate with this vector a quaternion with integer coefficients,
$$ q_{\mathbf v} = a + bi + cj + dk.  $$
Construct $4$-vectors for the quaternions $iq_{\mathbf v}$, $jq_{\mathbf v}$, and $kq_{\mathbf v}$. The dot-product of two $4$-vectors $\mathbf v, \mathbf w$ will simply be $\mathrm{Re}(q_{\mathbf v}^\ast q_{\mathbf w})$, where $a^\ast$ is the conjugate of $a$; by construction $\{q_{\mathbf v}, iq_{\mathbf v}, jq_{\mathbf v}, kq_{\mathbf v}\}$ are orthogonal in this sense, so the four vectors form an orthonormal set modulo $N$. One then takes $M$ the be the matrix with these four vectors as its columns: following the Wikipedia section on real matrix representations of quaternions, the explicit matrix representation is then
$$ \begin{bmatrix} a & -b & -c & -d \\ b & a & d & -c \\ c & -d & a & b \\ d & c & -b & a \end{bmatrix}.$$
(The determinant of this matrix will be $\| \mathbf v \|_2^4 = (a^2 + b^2 + c^3 + d^2)^2$.)
