1
$\begingroup$

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<i$ 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?

$\endgroup$
2
$\begingroup$

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<j$ 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<j\le k$ 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).$$
| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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$? $\endgroup$ – W. G. May 4 '19 at 15:24
  • 1
    $\begingroup$ @W.G. Sorry, I didn't notice that you hadn't proved that part. See the (new) first paragraph of my answer. $\endgroup$ – Misha Lavrov May 4 '19 at 17:46
  • $\begingroup$ That makes sense! Thank you for adding that great explanation there! $\endgroup$ – W. G. May 5 '19 at 3:10
  • $\begingroup$ 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. $\endgroup$ – W. G. May 8 '19 at 23:29
0
$\begingroup$

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<i$ or $\sigma(i)\leq k$ holds true.

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

Assume $k<i$ 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<i$ 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<i$ 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<i$ 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<j$ (i.e. because $(i,j)$ is an inversion here), we know $k<i<j\implies \sigma(j)>k$, too.

$\bullet$ Case 2.2: Else, if $j\leq k$ holds true, we know that $i<j\leq k$. 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<k$ here. Clearly, $(i,j)$ is an inversion in $\pi$ as it was an inversion in $\sigma$ looking at how we defined $\pi$ earlier.

| cite | improve this answer | |
$\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.