# Factoring a matrix as the product of block triangular and diagonal matrices.

How can I check that the matrix

$$K = \left[\begin{array}{c|cc} 1 & 0^{\mathrm T}_m & m \mathbf u^{\mathrm T} \\ \hline 0_m & I_m & I_m \\ m \mathbf u & I_m & O_m \end{array}\right] = \begin{bmatrix} 1 & \textbf{w}^T \\ \textbf{w} & B \\ \end{bmatrix}$$

can be factored as the following product of block triangular and diagonal matrices:

$$$$K = \begin{bmatrix} 1 & \textbf{w}^{T}B^{-1} \\ \textbf{0} & I_{2m}\\ \end{bmatrix} \begin{bmatrix} s & \textbf{0}^T\\ \textbf{0} & B\\ \end{bmatrix} \begin{bmatrix} 1 & \textbf{0}^{T}\\ B^{-1}\textbf{w} & I_{2m} \end{bmatrix}$$$$

where $$B = \begin{bmatrix} I_m & I_m \\ I_m & O_m \end{bmatrix} = \begin{bmatrix} 1 I_m & 1 I_m \\ 1 I_m & 0 I_m \end{bmatrix} = \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix} \otimes I_m.$$ and

$$\mathbf w = \begin{bmatrix} 0_m \\ m \mathbf u \end{bmatrix} = \begin{bmatrix} 0 \mathbf u \\ m \mathbf u \end{bmatrix} = \begin{bmatrix} 0 \\ m \end{bmatrix} \otimes \mathbf u$$ where $$\mathbf u = \begin{bmatrix} 1 \\ \vdots \\ 1 \end{bmatrix} \in \mathbb R^m$$ and I need to specify $$s$$. I think i have calculated the inverse of the Kronecker product $$B$$ correctly as $$B^{-1} = \begin{bmatrix} 0 & 1 \\ 1 & -1 \end{bmatrix} \otimes I_m = \begin{bmatrix} 0I_{m} & 1I_{m} \\ 1 I_{m} & -1I_{m} \end{bmatrix}$$ but I don't know where to go from here. Any help would be great!

• What is preventing you from computing the product ? – nicomezi Mar 3 '19 at 10:11
• I keep getting hopelessly lost with the algebra when i'm trying to compute the product? – user649959 Mar 3 '19 at 11:07

It works. To multiply

$$$$K = \begin{bmatrix} 1 & \textbf{w}^{T}B^{-1} \\ \textbf{0} & I_{2m}\\ \end{bmatrix} \begin{bmatrix} s & \textbf{0}^T\\ \textbf{0} & B\\ \end{bmatrix} \begin{bmatrix} 1 & \textbf{0}^{T}\\ B^{-1}\textbf{w} & I_{2m} \end{bmatrix}$$,$$

start, e.g., by multiplying the last two matrices. Perform block-wise multiplication like regular matrix multiplication. You get:

\begin{align} K &= \begin{bmatrix} 1 & \textbf{w}^{T}B^{-1} \\ \textbf{0} & I_{2m}\\ \end{bmatrix} \begin{bmatrix} s + \textbf{0}^T B^{-1} \textbf{w} & s \textbf{0}^T + \textbf{0}^T I\\ \textbf{0} 1 + B B^{-1} w & \textbf{0}\textbf{0}^T + B I \\ \end{bmatrix} \\ & = \begin{bmatrix} 1 & \textbf{w}^{T}B^{-1} \\ \textbf{0} & I_{2m}\\ \end{bmatrix} \begin{bmatrix} s & \textbf{0}^T \\ w & B \\ \end{bmatrix} \end{align}.

Keep going the same way:

\begin{align} & K &= \begin{bmatrix} s + \textbf{w}^{T}B^{-1}\textbf{w} & 1\textbf{0}^T + \textbf{w}^T B^{-1} B \\ \textbf{0} s + I \textbf{w} & \textbf{0}\textbf{0}^T + B\\ \end{bmatrix} = \begin{bmatrix} s + \textbf{w}^{T}B^{-1}\textbf{w} & \textbf{w}^T \\ \textbf{w} & B \\ \end{bmatrix} \end{align}.

This is equal to your desired $$K$$ if $$s + \textbf{w}^{T}B^{-1}\textbf{w} =1$$. Let us evaluate $$\textbf{w}^{T}B^{-1}\textbf{w}$$:

\begin{align} \textbf{w}^{T}B^{-1}\textbf{w} &= \left( \begin{bmatrix}0\\m\end{bmatrix} \otimes \textbf{u}\right)^T \left( \begin{bmatrix}0 & 1\\1&-1\end{bmatrix} \otimes I_m\right) \left( \begin{bmatrix}0\\m\end{bmatrix} \otimes \textbf{u}\right)\\ &= \left( \begin{bmatrix}0, m\end{bmatrix} \cdot \begin{bmatrix}0 & 1\\1&-1\end{bmatrix} \cdot \begin{bmatrix}0\\m\end{bmatrix} \right) \otimes \left( \textbf{u}^T I_m \textbf{u}\right) \\ & = [m, -m] \cdot \begin{bmatrix}0\\m\end{bmatrix}\cdot m = -m^2 \cdot m = -m^3. \end{align},

where we used the fact that $$(A \otimes B) \cdot (C \otimes D) = (AC \otimes BD)$$ if dimensions comply.

Therefore, your desired $$s$$ must satisfy $$s -m^3=1$$, i.e., $$s = 1+m^3$$.