Why the product of at most $n(n-1)/2$ Givens rotations can represent a rotation matrix?

Question

As title. Real orthogonal matrix with determinant 1 is an rotation matrix, right? I saw the saying like in another question or this paper, but it seems everyone just claim so. Why the upper bound is $n(n-1)/2$? Thanks in advance.

The definition of Givens rotations follows the Wikipedia page.

Answer 1

An $n\times n$ matrix has $n^2$ elements of which $n$ are on the diagonal so there are $n^2- n= n(n-1)$ off-diagonal elements. IF

Answer 2

Basically, it's because there are $n(n-1)/2$ off-diagonal entries in the strictly lower/upper triangular part, and a triangular orthogonal matrix must be diagonal.

We can prove the statement by mathematical induction. The base case $n=1$ is trivial. In the inductive step, let $n\ge2$. For convenience, if $\mathcal I$ is a subset of $\{1,2,\ldots,n\}$, denote by $\mathcal I^c$ its complement.

Suppose $A\in SO(n,\mathbb R)$. Then $A$ must contain some nonzero entries on its first column. Let $i$ be the largest index such that $A_{i1}\ne0$. If $i=1$ (i.e. if all off-diagonal entries on the first column are zero), let $G_1=I$. Otherwise, let $(c,s)=\frac{(A_{11},A_{i1})}{\| (A_{11},A_{i1})\|}\in\mathbb R^2$. Define a Givens rotation $G_1$ by \begin{aligned} G_1([1,i],[1,i])&=\pmatrix{c&s\\ -s&c},\\ G_1([1,i]^c,[1,i]^c)&=I_{n-2} \end{aligned} and define $A_1=G_1A$. Then $A_1\in SO(n,\mathbb R)$ and the first entry on the first column of $A_1$ is positive. Moreover, note that $(A_1)_{n1}$ must be zero. For, on one hand, if $i<n$, then $A_{n1}=0$ by the definition of the index $i$. Since $G_1$ modifies only the first and the $i$-th rows of $A$, $(A_1)_{n1}$ remains zero. On the other hand, if $i=n$, then $(A_{11},A_{n1})$ is parallel to $(c,s)$. Therefore $(A_1)_{n1}=-sA_{11}+cA_{n1}=0$.

Now, replace the role of $A$ by $A_1$ and let $i$ be the largest index such that $(A_1)_{i1}\ne0$. We can similarly find a Givens rotation $G_2$ and define $A_2=G_2A_1$ such that the $(A_2)_{n-1,1}=0,\ (A_2)_{11}>0$ and $G_2([1,i]^c,[1,i]^c)=I_{n-2}$. Since $G_2$ modifies only the first and the $i$-th rows of $A_2$, all other rows of $A_2$ are identical to those of $A_1$. In particular, $(A_2)_{n1}=(A_1)_{n1}$ is also zero. So, the last two entries on the first column of $A_2$ are both zero.

Continue in this manner, we can kill off the off-diagonal entries on the first column of $A$ one by one by left-multiplying it with more and more Given rotations. More precisely, there exist $n-1$ Givens rotations such that all off-diagonal entries on the first column $A_{n-1}=G_{n-1}G_{n-2}\cdots G_nA$ are zero. That is $A_{n-1}$ is a block-triangular matrix whose off-diagonal entries on the first column are zero. However, since $A\in SO(n,\mathbb R)$, so must be $A_{n-1}$. Therefore $A_{n-1}$ must be a block-diagonal matrix. As we have always kept the first diagonal entry of each $A_i$ positive, we must have $$ A_{n-1}=\pmatrix{1&0\\ 0&B} $$ where $B\in SO(n-1,\mathbb R)$. By induction hypothesis, $B$ is a product of at most $(n-1)(n-2)/2$ Givens rotations in $SO(n-1,\mathbb R)$. Hence $A$ is the product of at most $(n-1)+\frac{(n-1)(n-2)}{2}=\frac{n(n-1)}{2}$ Givens rotations.