Largest eigenvalue of product of orthogonal-projection rank-1 perturbation

Question

Suppose I have a symmetric positive definite matrix $A \in \mathbb{R}^{n \times n}$ with $n$ linearly indepedent columns $a_1,...a_n$ in $\mathbb{R}^n$. All columns $a_i$ has norm 1, but they are not orthogonal. Consider $P_i = I-a_ia_i^{'}$, which is an orthogonal projection to the orthogonal complement of $a_i$. I want to find the norm (or largest eigenvalue since they are the same) of the symmetric matrix $$P = P_1...P_{n-1}P_nP_{n-1}....P_1$$

Obviously the norm of $P$ is less than or equal to 1, since all $P_i$ has norm 1. If A is an orthonormal matrix, then $P=0$ since every $P_i$ eliminates a indepedent direction in $\mathbb{R}^n$. But for general case, where A is an arbitary matrix with unit column norm, things are unclear.

If any of the $P_i$ are removed from the product to form $\hat{P}$ (for example, $\hat{P}$ is obtained by removing the $P_1$ on left and right from the product), then the norm of $P'$ is exactly 1. This makes sense because in this case, we can find a vector that is in orthogonal complement of $span\{a_2,...,a_n\}$ and it is easy to check this vector is an eigenvector of $\hat{P}$ with eigenvalue 1.

Some observations are obtained from numerical experiments. If I let $A$ to be randomly generated PD matrix whose columns has norm 1, then P has rank n-1.And the norm of $P$ is usually very close to 1 (>0.99 in all trys). However, these results are certainly not general, considering matrix A with orthonormal columns.

Any thoughts that can explain the result of the numerical experiments? And any idea on finding the norm of $P$ given a particular A? Intuitively it has something to do with the norm of A, but I am not sure. Thanks!

Answer 1

Take a vector $v$ orthogonal to the first $n-1$ $a_i$. The squared norm of $P_nP_{n-1}...P_1v$ is $1-<a_n,v>^2$. Now if the $a_i$'s are independent and uniformly distributed, the expected value of $<a_n,v>^2$ is $1/n$. This is because you can complete $a_n$ in an orthonormal basis $b_i$, and the $<b_i,v>^2$ all have the same expectation, the sum of these expectations being $1$. In fact, it can be shown that the probability that $<a_n,v>^2$ exceeds $1/n$ by a margin $x$ decays very rapidly with $x$ (this is the concentration of measure phenomenon), which explains why you see this in all trials. Now in your case it is slightly different because of the constraint that the matrix is positive definite, so a more delicate argument is required, but basically the idea is similar.