# 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$$.

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.$$

• Thanks that helps a lot! Just one question for clarification. The orthogonal complement of the column space of X is the same as the null space of X, isnt it ? Commented Apr 13, 2021 at 17:54
• The orthogonal complement of the column space of $X$ is the null space of $X^T$, which is sometimes referred to as the "left nullspace" of $X$. Commented Apr 13, 2021 at 17:55

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}$$