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.