Alex L. Wang – Eigenvalues of block matrices with upper triangular blocks

This past week, Rujun Jiang and I posted a preprint on almost simultaneously diagonalizable quadratic forms (and other related ideas). At some point in the future, I will try write a short expository blog post about the main contributions of this work. Today, I’m simply going to present a neat factI don’t claim that this is new in any way and imagine this fact is known somewhere. On the other hand, I was personally unable to find a reference for it and would appreciate if anyone had pointers for me! about the eigenvalues of block matrices with upper triangular blocks that I needed/learned/proved while working on this project.

First, let’s define the sets of matrices we care about.

Definition 1. A matrix $T\in{\mathbb{C}}^{n \times m}$ is upper triangular if $\begin{aligned} m -j + i > \min(n,m) \implies T_{i,j} = 0.\end{aligned}$

Pictorially, an upper triangular matrix looks like $\begin{aligned} \begin{pmatrix} * & \cdots & *\\ & \ddots & \vdots\\ & & *\\ 0 & \cdots & 0\\ \vdots & \ddots & \vdots\\ 0 & \cdots & 0 \end{pmatrix}\quad\text{or}\quad \begin{pmatrix} 0 & \cdots & 0 & * & \cdots & *\\ \vdots & \ddots & \vdots & & \ddots & \vdots\\ 0 & \cdots & 0 & & & * \end{pmatrix}\end{aligned}$ when $n\geq m$ and $n\leq m$ respectively.

Suppose $(n_1,\dots,n_k)$ is such that $\sum_p n_p = n$ . Given $T\in{\mathbb{C}}^{n\times n}$ , we will let $[T]_{p,q}$ denote the $(p,q)$ th block of $T$ so that $[T]_{p,q} \in{\mathbb{C}}^{n_p\times n_q}$ .

Proposition 1. Let $(n_1,\dots,n_k)$ such that $\sum_p n_p = n$ and $T\in{\mathbb{C}}^{n\times n}$ such that $[T]_{p,q}$ is upper triangular for all $p,q\in[k]$ . Then, the determinant of $T$ depends only on the diagonal entries of blocks $[T]_{p,q}$ where $n_p = n_q$ .

Pictorially (for the case $(n_1,n_2,n_3) = (2,2,3)$ ), this proposition says that the determinant of a matrix with support $\begin{aligned} \left(\begin{array} {cc|cc|ccc} @ & * & @ & * & & * & *\\ & @ & & @ & & & *\\\hline @ & * & @ & * & & * & *\\ & @ & & @ & & & *\\\hline * & * & * & * & @ & * & *\\ & * & & * & & @ & *\\ & & & & & & @ \end{array}\right)\end{aligned}$

depends only on the entries in the $@$ positions.

At a high level, this proposition states that the determinant (whence also the characteristic polynomial and eigenvalues) of a block matrix with upper triangular blocks depends on only a very small number of entries of the block matrix.

I will now present a really neat proof of this fact using a proof strategy that Kevin Pratt suggested.

Proof. We will show the strongerThis stronger statement in fact implies that the permanent, or in fact any generalized matrix function, of such a matrix depends only on a small number of entries. statement: For any permutation $\sigma \in S_n$ , if $\prod_i T_{i,\sigma(i)}$ is nonzero, then for every $i$ , we have that $(i,\sigma(i))$ is a diagonal entry of some block $[T]_{p,q}$ where $n_p = n_q$ .

First assign a weight $w_i$ to each $i\in[n]$ : Given $i\in[n]$ , let $p$ denote the block containing $i$ and let $r$ denote position of $i$ within the $p$ th block. Set $\begin{aligned} w_i \coloneqq r - n_p/2.\end{aligned}$ Next for each $i,j\in[n]$ , assign the weight $w_{i,j}\coloneqq w_j - w_i$ .

Equivalently, if $i,j$ corresponds to $p,q,r,s$ , then set $\begin{aligned} w_{i,j} \coloneqq (s- r) + (n_p + n_q)/2 - n_q.\end{aligned}$

Next, as $T$ has upper triangular blocks, we also have that $\begin{aligned} T_{i,j}\neq 0 \implies (s-r) + \min(n_p,n_q) - n_q\geq 0.\end{aligned}$

We deduce that if $T_{i,j}\neq 0$ , then $w_{i,j}\geq 0$ . Furthermore, if $T_{i,j}\neq 0$ and $w_{i,j} = 0$ , then it must be the case that $n_p = n_q$ and $s = r$ .

Finally, note that for any permutation $\sigma\in S_n$ , we have $\begin{aligned} \sum_{i} w_{i,\sigma(i)} = \sum_i w_{\sigma(i)} - \sum_i w_i = 0.\end{aligned}$

This concludes the proof as then if $\prod_i T_{i,\sigma(i)}$ is nonzero, it must be the case that for all $i\in[n]$ , we have $T_{i,\sigma(i)}\neq 0$ and $w_{i,\sigma(i)} = 0$ . ◻

Intuitively, this proof looks at a matrix with upper triangular blocks and compares its support with some carefully constructed weighting of its entries. For $(n_1,n_2,n_3) = (2,2,3)$ , this looks like $\begin{gathered} \left(\begin{array} {cc|cc|ccc} * & * & * & * & & * & *\\ & * & & * & & & *\\\hline * & * & * & * & & * & *\\ & * & & * & & & *\\\hline * & * & * & * & * & * & *\\ & * & & * & & * & *\\ & & & & & & * \end{array}\right),\\ \left(\begin{array} {cc|cc|ccc} 0 & 1 & 0 & 1 & -0.5 & 0.5 & 1.5\\ -1 & 0 & -1 & 0 & -1.5 & -0.5 & 0.5\\\hline 0 & 1 & 0 & 1 & -0.5 & 0.5 & 1.5\\ -1 & 0 & -1 & 0 & -1.5 & -0.5 & 0.5\\\hline 0.5 & 1.5 & 0.5 & 1.5 & 0 & 1 & 2\\ -0.5& 0.5 & -0.5 & 1.5 & -1 & 0 & 1\\ -1.5 & -0.5 & -1.5 & -0.5 & -2 & -1 & 0 \end{array}\right).\end{gathered}$ The proof then observes that: The support of $T$ corresponds exactly to the entries with nonnegative weight. Additionally, the intersection of the support of $T$ with the entries of weight zero is exactly the set of diagonal entries of blocks $[T]_{p,q}$ where $n_p = n_q$ .

In the setting of our paper, we have that the blocks of $T$ are furthermore Toeplitz, i.e., their entries are constant along each diagonal. Then using the above proposition (along with other more elementary facts), we are then able to make crazy-looking statements such as $\begin{aligned} \begin{pmatrix} a & * & b & * & & * & *\\ & a & & b & & & *\\ c & * & d & * & & * & *\\ & c & & d & & & *\\ * & * & * & * & e & * & *\\ & * & & * & & e & *\\ & & & & & & e\\ \end{pmatrix} &\stackrel{\sigma}{=} \begin{pmatrix} a & & b & & & & \\ & a & & b & & & \\ c & & d & & & & \\ & c & & d & & & \\ & & & & e & & \\ & & & & & e & \\ & & & & & & e\\ \end{pmatrix}\\ &\stackrel{\sigma}{=} \begin{pmatrix} a & b&\\ c & d&\\ &&e \end{pmatrix},\end{aligned}$ where $\stackrel{\sigma}{=}$ indicates that the matrices have the same spectrum.