Block matrix decompositions

• The main formula we need concerns the inverse of a block matrix:
  

  $$\left[\begin{array}{cc} A & B \\ C & D \end{array}\right]^{-1} = ??$$

  
  We take the scenic route, obtaining several other results that will be useful later. In fact, mostly the entire theory of recursive algorithms for autoregressive modeling comes from these block matrix results. The development follows that of Appendix A in [KSH00]: We omit many extensions.

• Consider the matrix-vector equation:
  

  $$\left[\begin{array}{cc} A & B \\ C & D \end{array}\right] \left[\begin{array}{c} E \\ F \end{array}\right] = \left[\begin{array}{c} G \\ H \end{array}\right]$$

  
  Interpreting as two equations, if we multiply the top equation by $-CA^{-1}$ and add to the bottom we eliminate $E$, obtaining:
  

  $$(D-CA^{-1}B) F = H$$

  
  which is easily solved for $F$. The quantity $(D-CA^{-1}B)$ is called the Schur complement of $A$ and will be denoted $S_{A}$). To solve for $E$, we take our solution for $F$ and substitute in to the top equation, which has been left alone: $A E + B F = G$.

• The elimination step is equivalent to multiplying (both sides) on the left by a matrix $L$, and the substitution step (using $(D-CA^{-1}B) F$ rather than $F$) is equivalent to multiplying on the right by $U$ where
  

  $$L = \left[\begin{array}{cc} I & 0 \\ -CA^{-1} & I \end{array}\right]$$

  $$U = \left[\begin{array}{cc} I & -A^{-1}B \\ 0 & I \end{array}\right]$$

  
  
• According to the elimination and substitution steps, these matrices block-diagonalize the original matrix:
  

  $$\left[\begin{array}{cc} I & 0 \\ -CA^{-1} & I \end{array}\right]... ...array}\right] \left[\begin{array}{cc} I & -A^{-1}B \\ 0 & I \end{array}\right] = \left[\begin{array}{cc} A & 0 \\ 0 & S_{A} \end{array}\right]$$

  
  
• Note that to reverse the action of adding a multiple of one equation to another, we subtract that multiple. Hence, we may write:
  

  $$\left[\begin{array}{cc} A & B \\ C & D \end{array}\right] = \left[\begin{array}{cc} I & 0 \\ CA^{-1} & I \end{array}\right] ... ...{array}\right] \left[\begin{array}{cc} I & A^{-1}B \\ 0 & I \end{array}\right]$$ (14)

  
  
• Alternatively, we could have done the elimination step by adding a multiple ($-BD^{-1}$) of the bottom equation to the top. This gives a second block decomposition:
  

  $$\left[\begin{array}{cc} A & B \\ C & D \end{array}\right] = \left[\begin{array}{cc} I & BD^{-1} \\ 0 & I \end{array}\right] ... ...{array}\right] \left[\begin{array}{cc} I & 0 \\ D^{-1}C & I \end{array}\right]$$ (15)

  
  where $S_{D} = A-BD^{-1}C$ is the Schur complement of $D$.

• From the block decompositions we get inversion formulas:
  

  $$\left[\begin{array}{cc} A & B \\ C & D \end{array}\right]^{-1} = \left[\begin{array}{cc} I & -A^{-1}B \\ 0 & I \end{array}\right]... ...array}\right] \left[\begin{array}{cc} I & 0 \\ -CA^{-1} & I \end{array}\right]$$

  $$= \left[\begin{array}{cc} A^{-1} + A^{-1}BS^{-1}_{A}CA^{-1} & -A^{-1}BS^{-1}_{A} \\ -S^{-1}_{A}CA^{-1} & S^{-1}_{A} \end{array}\right]$$ (16)

  
  
  

  $$\left[\begin{array}{cc} A & B \\ C & D \end{array}\right]^{-1} = \left[\begin{array}{cc} I & 0 \\ -D^{-1}C & I \end{array}\right]... ...array}\right] \left[\begin{array}{cc} I & -BD^{-1} \\ 0 & I \end{array}\right]$$

  $$= \left[\begin{array}{cc} S^{-1}_{D} & -S^{-1}_{D}BD^{-1} \\ -D^{-1}CS^{-1}_{D} & D^{-1} + D^{-1}CS^{-1}_{D}BD^{-1} \end{array}\right]$$ (17)

  
  
• Matrix inversion lemma An important result comes by equating block elements of the two inversion formulas, e.g:
  

  $$(A\!-\!B D^{-1} C)^{-1}\! =\! A^{-1}\!+\!A^{-1} B (D\!-\!C A^{-1} B)^{-1} C A^{-1}$$ (18)

  
  
• The matrix inversion lemma arises naturally when considering any time-update step. Time updates to $(TT^{*})^{-1}$ involve adding a block column to $T$, e.g. $T_{N} \rightarrow T_{N+1} = [T_{N} \vert t_{N+1}]$. Hence $(T_{N+1}T^{*}_{N+1})^{-1} = (T_{N}T^{*}_{N} + t_{N+1} t^{*}_{N+1})^{-1}$. Here (18) obtains an efficient way for inverting the sum $T_{N}T^{*}_{N} + t_{N+1} t^{*}_{N+1}$