# Determinant of Lower Triangular Block Matrix (Proof Question: Decomposition)

I am wanting to prove the determinant of a block lower triangular matrix is the product of its diagonals. [Note, I am looking at Zilin J's answer here and asked the following question yesterday about it. However, I am still stuck on the part as to why there are two "decompositions" of functions here where $$\sigma=\pi \tau$$ (see the third bullet down).]

$$\begin{eqnarray}\det B &=& \sum_{\sigma\in S_{n+k}}\operatorname{sgn}\sigma\prod_{i=1}^k b[i,\sigma(i)]\prod_{ i=k+1}^{k+n} b[i,\sigma(i)] \tag{1}\\ \end{eqnarray}$$

Looking at equation $$(1)$$, if $$i\leq k$$ and $$\sigma(i)>k$$, then we have a zero summand as $$b[i,\sigma(i)]=0$$.

-That means we $$\underline{\text{only}}$$ consider values of $$\sigma$$ where $$k or $$\sigma(i)\leq k$$ holds true.

$$\bullet$$ [Show $$\pi \in S_k$$.] Now, let $$\pi(i):=\sigma(i)$$ for $$i\leq k$$. Since $$i\leq k$$, we know $$\sigma(i)\leq k$$ must hold true which means $$\pi(i)\leq k$$. So, $$\pi\in S_k$$.

$$\bullet$$ [Show $$\tau \in S_n$$.] Now, let $$\tau(i):=\sigma(k+i)-k$$ for $$i\leq n$$. Since $$\sigma(k+i)\leq k+n$$, we know $$\tau(i)=\sigma(k+i)-k\leq k+n-k=n$$. Thus, $$\tau \in S_n$$.

$$\bullet$$ [Show $$\operatorname{sgn}\sigma=\operatorname{sgn}\tau \operatorname{sgn}\pi$$. ]

Where do I go from here?

First, we know a bit more about $$\sigma$$. For every $$i$$ with $$i \le k$$, we know $$\sigma(i) \le k$$, so $$\sigma$$ maps the values $$\{1,2,\dots,k\}$$ to $$\{1,2,\dots,k\}$$ (in some order). But this "uses up" all the values in that range as possible values of $$\sigma(i)$$. So $$\sigma$$ must map the values $$\{k+1,k+2,\dots,n\}$$ to $$\{k+1,k+2,\dots,n\}$$ (in some order). In other words, if $$i>k$$, we know $$\sigma(i)>k$$, too.

The parity $$\operatorname{sgn}(\sigma)$$ can be defined in two ways:

1. As $$(-1)^x$$ where $$x$$ is the number of inversions in $$\sigma$$: pairs $$(i,j)$$ with $$i but $$\sigma(i) > \sigma(j)$$.
2. As $$(-1)^y$$ where $$y$$ is length of a representation of $$\sigma$$ as a product of transpositions (length-$$2$$ cycles).

Both of these can be used to show that $$\operatorname{sgn}(\sigma) = \operatorname{sgn}(\tau)\operatorname{sgn}(\pi)$$, so you get two proofs in one answer.

1. For every pair $$(i,j)$$ with $$i \le k$$ and $$j > k$$, we have $$\sigma(i) \le k$$ and $$\sigma(j) > k$$, so no such pairs are inversions. Therefore the inversions in $$\sigma$$ are pairs $$(i,j)$$ with $$i and $$\sigma(i) > \sigma(j)$$ - the inversions in $$\pi$$ - and pairs $$(i,j)$$ with $$k < i < j$$ and $$\sigma(i) > \sigma(j)$$ - the inversions in $$\tau$$. If there are $$x_1$$ inversions in $$\pi$$ and $$x_2$$ inversions in $$\tau$$, then $$\operatorname{sgn}(\sigma) = (-1)^{x_1 + x_2} = (-1)^{x_1} (-1)^{x_2} = \operatorname{sgn}(\pi) \operatorname{sgn}(\tau).$$
2. If we represent $$\pi$$ as a product of $$y_1$$ transpositions and $$\tau$$ as a product of $$y_2$$ transpositions, then we can find a representation of $$\sigma$$ as a product of $$y_1 + y_2$$ transpositions: the transpositions representing $$\pi$$, together with a translation to the range $$k+1, \dots, n$$ of the transpositions representing $$\tau$$. Therefore $$\operatorname{sgn}(\sigma) = (-1)^{y_1 + y_2} = (-1)^{y_1} (-1)^{y_2} = \operatorname{sgn}(\pi) \operatorname{sgn}(\tau).$$
• I can't believe you answered my question $\underline{\text{two}}$ ways here! That is AWESOME you did that both ways here; I appreciate that!!! Thank you! I was going through the very first sentence of the first way you did the proof, and I just wanted to know how you deduced $\sigma(j)>k$. We were assuming way earlier in the proof that $k<i$ or $\sigma(i)\leq k$ must hold true. You then wrote "For every pair $(i,j)$ with $i \le k$ and $j > k$", which means $\sigma(i)\leq k$ must hold true. But how do you know $\sigma(j)>k$? May 4 '19 at 15:24
• @W.G. Sorry, I didn't notice that you hadn't proved that part. See the (new) first paragraph of my answer. May 4 '19 at 17:46
• That makes sense! Thank you for adding that great explanation there! May 5 '19 at 3:10
• I know this question was asked a while ago but how did you show the inversions in $\tau$ and $\pi$ are linked with inversions in $\sigma$ here? I don't think it's a bijection where you take an inversion in $\sigma$ and map it to an inversion in $\tau$ or $\pi$. I'm just having a hard time with the mapping here and I posted kind of where I was at now. May 8 '19 at 23:29

I'm just adding the following as notes.

$$\begin{eqnarray}\det B &=& \sum_{\sigma\in S_{n+k}}\operatorname{sgn}\sigma\prod_{i=1}^k b[i,\sigma(i)]\prod_{ i=k+1}^{k+n} b[i,\sigma(i)] \tag{1}\\ \end{eqnarray}$$

Looking at equation $$(1)$$, if $$i\leq k$$ and $$\sigma(i)>k$$, then we have a zero summand as $$b[i,\sigma(i)]=0$$.

-That means we $$\underline{\text{only}}$$ consider values of $$\sigma$$ where $$k or $$\sigma(i)\leq k$$ holds true.

$$\bullet$$ [Show $$\pi \in S_k$$.]

Assume $$k or $$\sigma(i)\leq k$$ holds true.

Now, note for every $$j$$ with $$j \leq k$$, we know $$\sigma(j) \leq k$$, so $$\sigma$$ maps the values $$\{1,2,\dots,k\}$$ to $$\{1,2,\dots,k\}$$ (in some order). But this "uses up" all the values in that range as possible values of $$\sigma(j)$$. So $$\sigma$$ must map the values $$\{k+1,k+2,\dots,n\}$$ to $$\{k+1,k+2,\dots,n\}$$ (in some order). In other words, if $$j>k$$, we know $$\sigma(j)>k$$, too.

Let $$(i, j)$$ be an inversion in $$\sigma$$.

1. Suppose $$i\leq k$$ and $$j>k$$; show a contradiction. Thus, $$\sigma(i)\leq k$$ must hold true by our assumtion at the top. Also, note that $$\sigma(j)>k$$ holds true too (see above yellow portion). Thus, $$\sigma(i)\leq k<\sigma(j)\implies\sigma(i)<\sigma(j)$$. But this is a contradiction as $$\sigma(j)<\sigma(i)$$ by definition of an inversion. Thus, no inversions occur given this supposition.

2. Else, we know $$k or $$j\leq k$$ must hold true.

Now, let $$\pi(i):=\sigma(i)$$ for $$i\leq k$$. Since $$i\leq k$$, we know $$\sigma(i)\leq k$$ must hold true which means $$\pi(i)\leq k$$. So, $$\pi\in S_k$$.

$$\bullet$$ [Show $$\tau \in S_n$$.] Now, let $$\tau(i):=\sigma(k+i)-k$$ for $$i\leq n$$. Since $$\sigma(k+i)\leq k+n$$, we know $$\tau(i)=\sigma(k+i)-k\leq k+n-k=n$$. Thus, $$\tau \in S_n$$.

$$\bullet$$ [Show $$\operatorname{sgn}\sigma=\operatorname{sgn}\tau \operatorname{sgn}\pi$$. ]

Assumption: We showed earlier we are safe to assume $$k or $$\sigma(i)\leq k$$ holds true; we will assume this now for the remainder of the proof.

Now, note for every $$j$$ with $$j \leq k$$, we know $$\sigma(j) \leq k$$, so $$\sigma$$ maps the values $$\{1,2,\dots,k\}$$ to $$\{1,2,\dots,k\}$$ (in some order). But this "uses up" all the values in that range as possible values of $$\sigma(j)$$. So $$\sigma$$ must map the values $$\{k+1,k+2,\dots,n\}$$ to $$\{k+1,k+2,\dots,n\}$$ (in some order). In other words, if $$j>k$$, we know $$\sigma(j)>k$$, too.

Let $$(i, j)$$ be an inversion in $$\sigma$$.

1. Suppose $$i\leq k$$ and $$j>k$$; show a contradiction. Thus, $$\sigma(i)\leq k$$ must hold true by our assumtion at the top. Also, note that $$\sigma(j)>k$$ holds true too (see above yellow portion). Thus, $$\sigma(i)\leq k<\sigma(j)\implies\sigma(i)<\sigma(j)$$. But this is a contradiction as $$\sigma(j)<\sigma(i)$$ by definition of an inversion. Thus, no inversions occur given this supposition.

2. Else, we know $$k or $$j\leq k$$ must hold true.

$$\bullet$$ Case 2.1: If $$i>k$$ holds true, then $$\sigma(i)>k$$ (yellow portion above). Also, as $$i (i.e. because $$(i,j)$$ is an inversion here), we know $$kk$$, too.

$$\bullet$$ Case 2.2: Else, if $$j\leq k$$ holds true, we know that $$i. And by the first sentence of the yellow part above, we know $$\sigma(i)\leq k$$ and $$\sigma(j)\leq k$$.

$$\textbf{How do you show for case 2.1 that this is an inversion in \tau?}$$

Now, define $$f(i):=i-k$$. [Show $$f(i)>0$$ and $$f(i)\leq n$$.] As $$i>k$$, we know $$f(i)=i-k>0$$. By way of contradiction, suppose $$f(i)>n$$; show a cotradiction. Well, then $$i-k>n\implies i>n+k$$ (a contradiction as $$i\leq n+k$$). Thus, $$\tau(f(i))$$ is well-defined for any $$i>k$$ in the domain of $$\sigma$$. This means $$\tau(f(i))=\tau(i-k)=\sigma(k+(i-k))-k=\sigma(i)-k$$ represents the composition of functions we want for any $$i>k$$ in the domain of $$\sigma$$.

Now, let $$(i,j)$$ be an arbitrary inversion in $$\sigma$$ where $$i>k$$. [Show it is an inversion in $$\tau$$.] Well, $$\tau(i)=\sigma(i)-k$$ and $$\tau(j)=\sigma(j)-k$$. Since $$(i,j)$$ is an inversion in $$\sigma$$, we know $$\sigma(i)<\sigma(j)$$. Thus, $$\sigma(i)-k<\sigma(j)-k$$. Thus, $$\tau(i)<\tau(j)$$ which means $$(i,j)$$ is also an inversion in $$\tau$$.

$$\textbf{And how do you show for case 2.2 that this is an inversion in \pi?}$$

Now, let $$(i,j)$$ be an arbitrary inversion in $$\sigma$$ where $$j\leq k$$. [Show it is an inversion in $$\pi$$. Note we just map these functions by $$g(i):=i$$ here.] Clearly, $$j here. Clearly, $$(i,j)$$ is an inversion in $$\pi$$ as it was an inversion in $$\sigma$$ looking at how we defined $$\pi$$ earlier.