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]$.


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}$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.