[proofplan] We prove the criterion by computing the entries of $A^\top A$. The $(i,j)$-entry of this product is exactly the Euclidean [inner product](/page/Inner%20Product) of the $i$-th and $j$-th columns of $A$. Thus the equation $A^\top A=I_n$ is equivalent entry-by-entry to saying that each column has squared norm $1$ and distinct columns have inner product $0$. [/proofplan]

[step:Compute the entries of $A^\top A$ as column inner products]Write $A=(a_{ki})_{1\leq k,i\leq n}$. For each $i\in\{1,\dots,n\}$, the $i$-th column is \begin{align*} v_i=(a_{1i},\dots,a_{ni})\in\mathbb{R}^n. \end{align*} By the definition of matrix multiplication, for every $i,j\in\{1,\dots,n\}$, \begin{align*} (A^\top A)_{ij}=\sum_{k=1}^n (A^\top)_{ik}A_{kj}=\sum_{k=1}^n a_{ki}a_{kj}. \end{align*} By the definition of the Euclidean inner product on $\mathbb{R}^n$, this is \begin{align*} (A^\top A)_{ij}=\langle v_i,v_j\rangle. \end{align*} In particular, for $i=j$, \begin{align*} (A^\top A)_{ii}=\langle v_i,v_i\rangle=|v_i|^2. \end{align*}[/step]

[guided]The point of the proof is to translate the matrix equation defining orthogonality into statements about columns. Write $A=(a_{ki})_{1\leq k,i\leq n}$, where $a_{ki}$ is the entry in row $k$ and column $i$. Then the $i$-th column of $A$ is the vector \begin{align*} v_i=(a_{1i},\dots,a_{ni})\in\mathbb{R}^n. \end{align*} Now fix indices $i,j\in\{1,\dots,n\}$. The $(i,j)$-entry of $A^\top A$ is obtained by multiplying row $i$ of $A^\top$ against column $j$ of $A$. Since row $i$ of $A^\top$ is column $i$ of $A$ written as a row, the matrix product gives \begin{align*} (A^\top A)_{ij}=\sum_{k=1}^n (A^\top)_{ik}A_{kj}=\sum_{k=1}^n a_{ki}a_{kj}. \end{align*} The Euclidean inner product of $v_i$ and $v_j$ is defined by \begin{align*} \langle v_i,v_j\rangle=\sum_{k=1}^n a_{ki}a_{kj}. \end{align*} Therefore \begin{align*} (A^\top A)_{ij}=\langle v_i,v_j\rangle. \end{align*} When $i=j$, this same identity becomes \begin{align*} (A^\top A)_{ii}=\langle v_i,v_i\rangle=|v_i|^2. \end{align*} Thus the diagonal entries of $A^\top A$ measure the squared lengths of the columns, while the off-diagonal entries measure the pairwise inner products of distinct columns.[/guided]

[step:Derive unit length and orthogonality of columns from $A\in O(n)$] Assume $A\in O(n)$. By the definition of the [orthogonal group](/page/Orthogonal%20Group), \begin{align*} A^\top A=I_n. \end{align*} Hence, for every $i,j\in\{1,\dots,n\}$, \begin{align*} \langle v_i,v_j\rangle=(A^\top A)_{ij}=(I_n)_{ij}. \end{align*} If $i=j$, then $(I_n)_{ii}=1$, so \begin{align*} |v_i|^2=\langle v_i,v_i\rangle=1. \end{align*} Since $|v_i|\geq 0$, it follows that $|v_i|=1$. If $i\neq j$, then $(I_n)_{ij}=0$, so \begin{align*} \langle v_i,v_j\rangle=0. \end{align*} Thus the columns of $A$ have unit Euclidean norm and are pairwise orthogonal. [/step]

[step:Recover $A^\top A=I_n$ from unit length and orthogonality of columns] Conversely, assume that $|v_i|=1$ for every $i\in\{1,\dots,n\}$ and that $\langle v_i,v_j\rangle=0$ whenever $i\neq j$. We compare the entries of $A^\top A$ and $I_n$. If $i=j$, then \begin{align*} (A^\top A)_{ii}=\langle v_i,v_i\rangle=|v_i|^2=1=(I_n)_{ii}. \end{align*} If $i\neq j$, then \begin{align*} (A^\top A)_{ij}=\langle v_i,v_j\rangle=0=(I_n)_{ij}. \end{align*} Therefore every entry of $A^\top A$ equals the corresponding entry of $I_n$, so \begin{align*} A^\top A=I_n. \end{align*} By the definition of the orthogonal group, $A\in O(n)$. This proves the converse implication and completes the proof. [/step]