6
$\begingroup$

There is an easy theorem in linear algebra that "successive Schur complementations compose nicely": for instance, let's say I have a matrix $$ M_0= \begin{bmatrix} A & B & C \\ D & E & F\\ G & H & I \end{bmatrix}, $$ with all blocks $n\times n$ in this and all the following formulas. I take the Schur complement of the leading diagonal submatrix $A$, to get $$ M_1= \begin{bmatrix} \hat{E} & \hat{F}\\ \hat{H} & \hat{I} \end{bmatrix}, $$ and then again the Schur complement of $\hat{I}$ in $M_1$, to get a matrix $\tilde{E}$. Then $\tilde{E}$ is the same as the Schur complement of $\begin{bmatrix}A & C\\ G & I\end{bmatrix}$ in $M_0$.

More in general, if I remove two sets of (disjoint) entries consecutively, then the result is the same as removing their union from the original matrix.

This result is difficult to write down properly in a more general version ("let $S$ and $T$ be two disjoint subsets of $\{1,2,\dots,n\}$..."), because after the first complement the numbering of the remaining rows and columns changes. I do need the general version where $S$ and $T$ are arbitrary subsets, so I can't get away with a statement like "without loss of generality, $S$ contains the first/last $k$ elements of $\{1,2,\dots,n\}$".

One of the ideas that come to mind is introducing an external labelling: if the block rows and columns are labelled $a,b,c$, then after removing $\{a\}$ the remaining ones are still labelled $(b,c)$. However this looks artificial and is definitely not standard in linear algebra (it is more usual in Markov chains, where Schur complements also appear).

How would you state this lemma formally in a paper? Is there a way out of this that I am overlooking?

$\endgroup$
7
  • 1
    $\begingroup$ Not sure what you mean by "entries" here. Would a wording using binary trees be of any use? This allows formalizing statements like "a product of $n$ elements of a ring is independent of the bracketing". $\endgroup$ Feb 23, 2014 at 21:46
  • $\begingroup$ I mean entries = row/column indices. I have edited, I hope it's clearer now. $\endgroup$ Feb 23, 2014 at 22:14
  • 1
    $\begingroup$ Ah! Then trees are probably not useful. I am still not fully sure what precisely you want to state, so I'm finding it difficult to give a hint (after taking the Schur complement of a $2\times 2$ submatrix, shouldn't you be left with a $2\times 2$ matrix? how do you then take another Schur complement of a $2\times 2$ submatrix?). $\endgroup$ Feb 24, 2014 at 16:59
  • 1
    $\begingroup$ @darijgrinberg if you have $M = \begin{bmatrix}A & B \\ C & D\end{bmatrix}$, then $A - B D^{-1}C$ is the Schur Complement of $D$, not of $A$. $\endgroup$
    – Paglia
    Feb 26, 2014 at 13:20
  • 1
    $\begingroup$ Over 5 years later, I think that the easiest solution is to deal always with matrices whose rows and columns are indexed by an arbitrary finite set, not necessarily $\{1, \dotsc, n\}$. Then the row and column indices of the $S$-Schur complement of an $I$-indexed matrix come from $I \setminus S$, which contains $T$; so that it makes perfectly good sense to speak of the $T$-Schur complement of this ($I \setminus S$)-matrix, which is $I \setminus (S \cup T)$: no need to re-index at any point. $\endgroup$
    – LSpice
    Sep 10, 2019 at 2:57

2 Answers 2

1
$\begingroup$

I think it follows directly from the Crabtree-Haynsworth quotient formula (cf. Zhang's book, p. 25). A detailed derivation is given in Section 6 of a 1983 Brualdi-Schneider paper.

$\endgroup$
2
  • $\begingroup$ The notation used in the "second proof" in Section 6 of Brualdi-Schneider assumes wlog that the Schur complements are of the leading or trailing submatrix, so this won't work. The notation $(A/E)/(K/E)$ is very appealing, but it seems to be ill-defined to me: if your matrix is $A=\begin{bmatrix}2 & 1 & 0\\ 0.9 & 2 & 0.8\\ 0 & 0.7 & 2\end{bmatrix}$ and $E=[2]$, what does $A/E$ mean? Trying to get my hands on the book now. $\endgroup$ Feb 24, 2014 at 10:06
  • $\begingroup$ Got the book, and it seems to have the same problem. $\endgroup$ Feb 24, 2014 at 10:07
1
$\begingroup$

Let us denote the Schur complement of $A$ relative to the set of indices $S$ with the expression $\mathcal{C}(A)_S$.

Here is my proposal (perhaps it is a bit cryptic!):

Let $A$ be an $n \times n$ matrix. Then, for any $S\subseteq\{1,\ldots,n\}$ with $|S|=k$ and $T \subseteq\{1,\ldots,n-k\}$ it holds $$\mathcal{C}(\mathcal{C}(A)_S)_T = \mathcal{C}(A)_{S \cup \sigma^{-1}(T+k)},$$ where $\sigma\in S_n$ is such that $\sigma(S) = \{1,\ldots,k\}$ and that $\left.\sigma\right|_{S}$ and $\left.\sigma\right|_{S^c}$ are monotonically increasing.

$\endgroup$

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.