# Solving for $L$, where $P_n \cdots P_1 = I - XLX^T$, with $\Vert x_i \Vert_2=1$, $P_i := I - 2x_i x_i^T$, $X=[x_1 \cdots x_n]$

## Problem

Solve for $$L$$, where $$P_n \cdots P_1 = I - XLX^T$$

where $$\Vert x_i \Vert_2=1$$, $$P_i := I - 2x_i x_i^T$$, and $$X_{m \times n} = [x_1 |\cdots | x_n]$$.

## Try

Note that $$L$$ is a lower triangular matrix. Denoting $$(i,j)$$ component of $$L$$ as $$L_{ij}$$, let us find $$L_{ij}$$'s explicitly. We have

\begin{align} P_n \cdots P_1 - I &= (I - 2x_nx_n^T) \cdots (I - 2x_1x_1^T) - I\\ &= - L_{11} x_1x_1^T - L_{21}x_2x_1^T - \cdots -L_{nn}x_nx_n^T \end{align}

where we can note that $$-L{ij}$$ is the coefficient for $$x_ix_j^T$$ in $$(I - 2x_nx_n^T) \cdots (I - 2x_1x_1^T)$$.

Let us observe more carefully. For $$L_{kk}$$'s, we have

$$L_{kk} = 2$$

since these terms only come from $$I \cdots I (-2x_kx_k^T) I \cdots I$$. Next, we note that

$$L_{(k+1)k} = -2^2$$

and, next,

$$-L_{(k+2)k} = 2^2 - 2^3(v_{k+2}^Tv_{k+1})(v_{k+1}^Tv_k)$$

but I cannot see any simpler rule for $$L_{ij}$$'s... Anyone to help me with finding all the $$L_{ij}$$s?

You can try to construct the matrix $$L$$ recursively. Let's we write $$X_k:=[x_1,\ldots,x_k]$$. Assume tat we have already a matrix $$L_k$$ such that $$P_k\cdots P_1=I-X_kL_kX_k^T.$$ Now let's see what happens if we multiply this by $$P_{k+1}$$: $$\begin{split} P_{k+1}\cdots P_1 &= (I-2x_{k+1}x_{k+1}^T)(I-X_kL_kX_k^T)\\ &= I-2x_{k+1}x_{k+1}^T-X_kL_kX_k^T+2x_{k+1}x_{k+1}^TX_kL_kX_k^T \end{split}$$ We would like to express this as follows: $$\begin{split} P_{k+1}\cdots P_1 &= I-X_{k+1}L_{k+1}X_{k+1}^T\\ &= I-[X_k,x_{k+1}]\begin{bmatrix}\tilde{L}_{k+1}&0\\l_{k+1}^T&\lambda_{k+1}\end{bmatrix}[X_k,x_{k+1}]^T\\ &= I-X_k\tilde{L}_{k+1}X_k^T-x_{k+1}l_{k+1}^TX_k^T-\lambda_{k+1}x_{k+1}x_{k+1}^T \end{split}$$ Comparing terms in the two expressions, we get $$L_{k+1} =\begin{bmatrix} L_k & 0\\ -2y_k^TL_k & 2 \end{bmatrix},$$ where $$y_k:=X_k^Tx_{k+1}$$. This gives a recursive formula for $$L=L_n$$.
If you are after an explicit formula, you can try to use this recursion and find $$L$$ in terms of the coefficients $$y_1,\ldots,y_{n-1}$$.