# Givens rotation with Eigendecomposition

Setup

Let $\Sigma_t$ be the time $t$ positive-definite covariance matrix of some $N$-dimensional random vector $X_t$. Denote $\Sigma_t = P_t \Lambda_t P_t$ be the spectral/eigen-decomposition of this covariance matrix. There are $N + {N \choose 2} = N(N+1)/2$ free elements in this matrix. There are $N$ positive eigenvalues, and the rest are in the eigenvectors.

Questions

I am wondering how a Givens rotation matrices will "isolate out" the ${N \choose2}$ "free" elements of the eigenvectors. A paper I am reading reads:

We further write each $P_t$ as a product of $N(N-1)/2$ Givens rotation matrices $P_t = \Pi_{i<j}G_{ij}(\omega_{i,j,t})$...

1. How should I visualize or understand the $N(N-1)/2$ free elements of $P_t$ before the Givens transformation. Probably something to do with orthogonality restrictions, right?
2. How do I visualize or understand what the Givens rotations are doing? I imagine that plotting each $w_{i,j,t}$ versus time $t$ leads to something nice looking.
• #2 is easy: columns of $P$ have unit length and are orthogonal. So the first column has $N-1$ degrees of freedom, the second has $N-2$ and so on until the last one has none, so overall it's $$\sum_{k=1}^N (N-k) = \sum_{k=1}^{N-1} k = \sum_{k=1}^N k - N = N(N+1)/2 -N = N(N-1)/2.$$ Feb 18 '17 at 19:47
• Regarding #3: Givens rotation is simply a rotation in a 2D plane spanned by two coordinate axes. Once this plane is fixed, Givens rotation only depends on 1 parameter: the angle of rotation. So one Givens rotation takes 1 degree of freedom. Composing $N(N-1)/2$ Givens rotations together allows to reproduce any arbitrary rotation matrix. In 3D this boils down to saying that you can reproduce any 3D rotation by rotating first around $x$ (i.e. in the YZ plane), then around $y$, and then around $z$. Take a matchbox and convince yourself that this true. Feb 21 '17 at 17:05
• @amoeba yeah this sounds right. Thanks for your help. I'll probably type something up with $\LaTeX$ later tonight Feb 21 '17 at 17:14
• Looking forward. By the way, if Q1 got basically dissolved, perhaps you should edit it out of your question altogether. It will only confuse future readers. I'd simply edit the quote to replace U with P. Feb 21 '17 at 17:15

@amoeba's comment answers the first thing question. This is all for the second. Let's suppress all the mentioning of $t$. Element $(k,l)$ of a Givens matrix $G_{i,j} \in \mathbb{R}^{N \times N}$ can be written as $$G_{i,j}[k,l] = \begin{cases} \cos(\omega_{i,j}) & i=j \text{ and } (i=k \text{ or } i = l) \\ \sin(\omega_{i,j}) & k=i \text{ and } l = j\\ -\sin(\omega_{i,j}) & k=j \text{ and } l = i \\ 1 & k = l \text{ and } k \neq i \text { and } k \neq j \\ 0 & \text{ otherwise } . \end{cases}$$

## Rotating a Vector

Wikipedia has a pretty good description about how the transpose of this matrix takes vectors and rotates them in the $i-j$ plane in a counterclockwise fashion.

Let $v \in \mathbb{R}^N$ be some vector. Picking the suitable angle $-2\pi \le \omega_{i,j} \le 2 \pi$ will zero out the $j$th element of this vector. It will also map the $i$th element of this vector to $\sqrt{v_i^2 + v_j^2}$. In other words: $$G_{i,j}^Tv = (v_1,\ldots,v_{i-1},\sqrt{v_i^2 + v_j^2},v_{i+1},\ldots,v_{j-1},0,v_{j+1},\ldots,v_n)^T.$$

## Rotating a Matrix

Think about rotating our orthogonal matrix $P = [P_1,\ldots,P_N]$ (remember no more $t$). The index $i$ will correspond with the column of $P$ we're talking about. Set $i=1$ for a second. Letting $j$ go from $2,\ldots,N$ we have $$G_{1,2}^T \cdots G_{1,N}^T P_1 = (1,0,\ldots,0)^T = e_1$$ where $e_n \in \mathbb{R}^N$ corresponds to a matrix of all zeros, except a $1$ in the $n$th spot. This is because this column is of unit length.

$G_{1,2}^T \ldots G_{1,N}^T$ affected $P_2$, but none of the other columns. By the same reasoning as above $$G_{2,3}^T\cdots G_{2,N}^T \cdot G_{1,2}^T \cdots G_{1,N}^T P_2 = e_2.$$ Also, $G_{2,3}^T\cdots G_{2,N}^T \cdot G_{1,2}^T \cdots G_{1,N}^T P_1 = e_1$ still, because rotating $(0,0)^T$ yields the same thing.

So you can proceed inductively and get $$\prod_{i<j}G_{i,j}^T P = [e_1,\ldots,e_N]= I,$$ and we can solve this and get $$P = [\prod_{i<j}G_{i,j}^T]^{-1} = \prod_{i<j}G_{i,j},$$ which is true as long as we're careful about ordering the $G_{i,j}$s correctly (recall that $G_{i,j}^T = G_{i,j}^{-1}$).

## Remaining Questions

I'm not still confident in interpreting individual $\omega_{i,j}$s. Also, these matrices don't commute with one another, so how do we choose the "right" order. There's no point incentive for accepting my own answer, so anyone, feel free to chip in here.