Condition for existence of an orthonormal matrix whose column space is orthogonal to the column space of another matrix While I was reading a statistics paper, I came across one statement that I don't understand (I just have basic linear algebra knowledge).
Assume (in the context of regressions), we have a $n\times p$ data matrix $X$, assuming that $X$ is invertible and $n>p$. The paper states
"$U \in \mathbb{R}^{n \times p}$ is an orthonormal matrix whose column space is orthogonal to that of $X$ s.t. $U^TX=0$": such matrix exists if $n\geq 2p$.
I don't understand where the last statement comes from.
I know that the nullspace of $X$ has dimension $n-rank(X)=n-p$  in full rank case and $U$ is the orthonormal basis of the null space of $X$. But I don't get the link why $U$ only exists, if $n\geq p +rank(X)$, i.e. $n\geq 2p$.
 A: Note: it is not standard to refer to the matrix $X$ as "invertible" unless $X$ is a square matrix. Presumably, "$X$ is invertible" refers in this case to the fact that $X$ has full rank. In this case, because $X$ is $n \times p$ with $n > p$, this means that $X$ has rank $p$ (i.e. has "full column rank").
As you say, "$U \in \mathbb{R}^{n \times p}$ is an orthonormal matrix whose column space is orthogonal to that of $X$". The fact that the column space is orthogonal to that of $X$ is equivalent to the statement that $U^TX = 0$. Because $U$ is $n \times p$ with orthonormal columns, the dimension of its column space is $p$. Because the column space of $U$ is orthogonal to that of $X$, the column space of $U$ must be a subspace of the orthogonal complement to the column space of $X$. The column space of $X$ is a $p$-dimensional subspace of $\Bbb R^n$, which means that its orthogonal complement has dimension $n-p$.
Putting all this together leads us to the following conclusion:
$$
\operatorname{col}(U) \subseteq \operatorname{col}(X)^\perp \implies\\
\dim(\operatorname{col}(U)) \leq \dim (\operatorname{col}(X)^\perp) \implies\\
p \leq n-p \implies\\
2p \leq n.
$$
A: not sure, but this could be a reason. Since $X$ is a non-square matrix, we can assume that there are $n-p$ rows that can be described as a linear combination of the other rows. Suppose we decompose $X$ into the following:
$$X = \begin{bmatrix}X_1 \\ AX_1\end{bmatrix}$$
Where $A \in (n-p)\times p$ represent these linear row transformations and $X_1$ is a full rank $p\times p$ matrix. The orthonormal matrix can then be decomposed to
$$U^T = \begin{bmatrix}U_1 & U_2\end{bmatrix}$$
Such that
$$U_1X_1 + U_2AX_1 = 0_{p\times p}$$
Next assume that $U_1$ is the orthonormal matrix of $X_1$
$$U_1X_1 = 0_{p\times p}$$
$$U_2 = U_1(A^TA)^{-1}A^T$$
Now as we know, if a matrix has more columns than rows, the product $A^TA$ is singular (and the inverse doesnt exist). Which means that in order to ensure the inverse exists, the amount of rows in $A$ must be larger or equal to $p$.
Alternatively, suppose $U_1X_1 \neq 0$:
$$-U_1X_1 = U_2AX_1$$
$$-U_1 = U_2A$$
$$-U_1A^T(AA^T)^{-1} = U_2$$
if $n<2p$, the inverse of $AA^T$ does exist, however, this does not yield a solution unless $A$ is square:
$$U_1X_1 -U_1A^T(AA^T)^{-1}AX_1 \neq 0_{p\times p}$$
