Row norms of a tall matrix with orthonormal columns

Question

Let $X$ be a $n \times k$ matrix with $n > k$. If the columns of $X$ are orthonormal, then I want to show that the row norms are bounded by 1. My current solutions involves completing $X$ into an orthogonal matrix and then using the fact that $X^T X = X X^T = I$. I would like a more direct argument such as assuming that a row has norm larger than one leads to an immediate contradiction.

Answer 1

This is just the Pythagorean theorem. Denote the column vectors by $f_1, \dots, f_k$ Let $e_j$ be the usual unit vector with $1$ in the $j$-th position. Then $$ e_j = \sum_{l = 1}^k \langle e_j, f_l\rangle \ f_l + u_j, $$ where $u_j$ is a vector perpendicular to the span of $f_1, \dots, f_k$. Hence $$ 1 = ||e_j||^2 = \sum_{l = 1}^k |\langle e_j, f_l\rangle |^2 + ||u_j||^2. $$ Hence $\sum_{l = 1}^k |\langle e_j, f_l\rangle |^2 \le 1$. Note that the $(j, l)$ entry of the matrix is $\langle f_l, e_j \rangle$.

Answer 2

The squared row norms of a matrix $X$ with orthonormal columns are also known as the leverage scores of $X$. See section 2.4 of Sketching as a Tool for Numerical Linear Algebra for another proof that each of these squared row norms is less than or equal to 1.