Are random circulant matrices almost orthonormal? Let $(X_1, X_2, \dots, X_n)$ be i.i.d. ${\cal N}(0,1)$. We construct a random circulant matrix $M$:
$$M = \frac{1}{\sqrt n}\begin{pmatrix}X_1 &X_2 &X_3 \dots &X_n\\ X_n &X_1 & X_2 \dots &X_{n-1}\\ \vdots &\vdots &\vdots &\vdots\\X_2 &X_3 &X_4 \dots &X_1\end{pmatrix}.$$
My questions are the following:


*

*Is $M$ "almost orthonormal" in a precise probabilistic sense?

*Related to above, is it possible to upper-bound the largest possible dot product between any two rows of $M$ by a suitably small $\epsilon_n$? 
Note that this says that $MM^T$ is close to the identity matrix $I_{n \times n}$, as we are bounding the off-diagonal entries of $MM^T$ by $\epsilon_n$, while the diagonal entries are close to $1$.  
 A: The diagonal elements of $P=\frac{1}{N}MM^T$, like
$$P_{11}=\frac{1}{N}\sum_{i=1}^NX_i^2,$$
satisfy $ \langle P_{11}\rangle=1$ and $ \langle P_{11}^2\rangle=1+2/N$ (variance decreases like $N^{-1}$).
On the other hand, off-diagonal elements like
$$P_{12}=\frac{1}{N}\sum_{i=1}^{N}X_iX_{i+1} $$
satisfy $ \langle P_{12}\rangle=0$ and $ \langle P_{12}^2\rangle=1/N$ (variance also decreases like $N^{-1}$).
In this sense I would say $P$ is close to the identity.
A: Marcel's solution provides a  good approach for understanding the marginal statistics.  Here are a few supplementary comments that might give a little insight into the joint distribution.
Let $D$ be the discrete Fourier transform matrix, i.e. the $j,k$-th entry is:
$$D_{j,k}=e^{-2\pi i jk/N}/\sqrt{N}$$
Consider the discrete Fourier transform of the first row of $M$, i.e.
$$(G_1,...,G_N)=(1/\sqrt{N})(X_1,...,X_N)D$$
Let $G$ be a diagonal matrix with diagonal entries $G_1,...,G_N$.
Then $D$ diagonalizes $M$ (see, e.g., this description), that is:
$$M = D G D^{-1}$$
If we took the $X_i$ to be complex-valued Gaussian variables, then we would be essentially done at this point: since $D$ is unitary, and the Gaussian is spherically symmetric, then the $G_i$ would be i.i.d. (complex) Gaussian random variables with mean 0 and variance $1/n$.  (That is, if we sampled the $G_i$ as i.i.d complex $\mathcal{N}(0,1/n)$, then $DGD^{-1}$ has the same distribution as samples from the original circulant matrix.)  It follows that
$$MM^*=(DGD^{-1})(DG^*D^{-1})=DGG^{-1}D^*$$
It then follows that the eigenvalues of $MM^{*}$ (or, if you prefer, the squared singular values of $M$) are distributed like $n$ i.i.d draws from a rescaled $\chi^2$ distribution with 2 degrees of freedom (which happens to simplify to an exponential distribution), where we rescale by dividing by $n$.  From an eigenvalue perspective, this is a complete characterization of the "orthonormality" of $M$.
However, your $X_i$ are probably real-valued.  This causes a small book-keeping headache, but doesn't really change much.  In brief: since the $X_i$ are real-valued, the $G_i$ will be symmetric.  We can convert our $n\times n$ complex-valued matrices into corresponding $2n \times 2n$ real-valued matrices (say, $D'$ and $G'$). Then observe that there are only $n$ of the $2n$ diagonal elements in $G$ are free, and only $n$ of the $2n$ inputs to $D'$ are non-zero (namely, the ones corresponding to the real values of the inputs in $D$).  Noting that the resulting decimated matrices are still unitary, we then reduce to the previous case, except with $\chi^2/n$ distributions with only 1 degree of freedom.
