4
$\begingroup$

I am trying to understand the ProofWiki proof of Laplace expansion for determinants.

I understand the first equation $$ D = \sum_{\sigma} {\rm sgn} (\rho) {\rm sgn} (\sigma) \prod_{j=1}^n a_{\rho(j), \sigma(j)} $$ $D$ is the determinant of $n$ by $n$ matrix $(a_{i,j})$ and $\rho$ is any permutation. but I don't understand the following step which states

$$ \small\sum_{\sigma}(−1)^{\tiny\displaystyle\sum^k_{i=1}(r_i+s_i)} {\rm sgn} (ρ(r_1,…,r_k)){\rm sgn} (σ(s_1,…,s_k)){\rm sgn} (ρ(r_{k+1},…,r_n)){\rm sgn} (σ(s_{k+1},…,s_n)) \prod_{j=1}^n a_{\rho(j), \sigma(j)} $$

Could someone kindly explain how to deduce this step? thank you

$\endgroup$
7
  • $\begingroup$ It is much more clearly explained on Wikipedia once you get past the permutation cycle notation section: en.wikipedia.org/wiki/Laplace_expansion#Proof $\endgroup$
    – FShrike
    Commented Apr 3, 2022 at 17:05
  • $\begingroup$ The proof in the link is for a special case, and I wanted to understand the proof of the general case, as in the link in the question..... $\endgroup$
    – Johnny T.
    Commented Apr 4, 2022 at 12:08
  • $\begingroup$ What special case? $\endgroup$
    – FShrike
    Commented Apr 4, 2022 at 13:15
  • $\begingroup$ @JohnnyT. the proof on Wikipedia is for the general case $n \times n$. $\endgroup$ Commented Apr 6, 2022 at 18:30
  • 1
    $\begingroup$ @AntoniParellada I have only just now truly seen what the question was asking. I now agree, it is different $\endgroup$
    – FShrike
    Commented Apr 7, 2022 at 7:08

1 Answer 1

1
+50
$\begingroup$

The wikiproof page in question uses a rather cryptic notation. The main point is the following: A partition of $\{1,...,n\}=H\sqcup H'$ into two subsets of (fixed) cardinalities $k$ and $n-k$, respectively, may be specified in a unique way through a permutation $r(1,...,n)=(r_1,...,r_k, r_{k+1},...r_n)$ where the ordered lists $r_1<\cdots < r_k$ and $r_{k+1} < \cdots <r_n$ run through the elements of the two subsets. Let $S_k(H) \times S_{n-k}(H')$ denote the set of permutations $\mu$ that shuffles elements within $H$ and within $H'$ but do not mix the two sets. Then every permutation $\rho\in S_n$ may be written in a unique way as $\rho=\mu\circ r$ for some $r$ and $\mu$ of the above-mentioned form.

An example with $n=5,k=2$ : Given the permutation $(1, 2, 3, 4, 5)\stackrel{\rho}\longrightarrow (5, 2; 4, 1, 3)$ (the semi-colon is just to underline the partitions) there is a unique splitting (with $H=\{2,5\}$, $H'=\{1,3,4\}$): $$(1, 2, 3, 4, 5) \stackrel{r}{\longrightarrow}(2, 5; 1, 3, 4) \stackrel{\mu}\longrightarrow (5, 2; 4, 1, 3). $$ In the equation you mention $\rho$ is any permutation but e.g. $\rho(r_1,...,r_k)$ is what I would prefer to call $\mu(r_1,...,r_k)$, since $\mu$ restricted to $\{r_1,...,r_k\}$ is indeed just a permutation of that set. Anyway, as $\mu$ is just the product of two permutations the signature of $\mu$ is the product of signatures (in the article writing $\rho$ instead of $\mu$), $$ {\rm sgn}(\mu(r_1,...,r_k)) \times {\rm sgn}(\mu (r_{k+1},...,r_n)).$$

For the signature of $r$ in my example you need $r_2-2= 5-2=3$ neighboring binary swaps to move five from position 2 to position 5 and then you need $r_1-1=1$ binary swap to move $2$ to position 2. Note that automatically this puts the remaining $n-k=3$ elements in the correct order! In general, the number of binary swaps is given by $$\sum_{i=1}^k (r_i-i)=\sum_{i=1}^k r_i - k(k+1)/2.$$ Thus, $${\rm sgn}(r)=(-1)^{\sum_{i=1} r_i} \times (-1)^{k(k+1)/2}.$$ Now use the same argument for the permutation of the second indices, $\sigma\circ s$. The last factor appears twice, but as $(-1)^{k(k+1)}=1$ it disappears and you obtain the formula you stated when you make the above interpretation of $\rho(r_1,...,r_k)$ etc. The sequel of the article makes sense when using this interpretation. Hope this helps.

$\endgroup$
7
  • $\begingroup$ "In the equation you mention $\rho$ is any permutation but e.g. $\rho(r_1,...,r_k)$ is what I would prefer to call $\mu(r_1,...,r_k)$, since $\mu$ restricted to $\{r_1,...,r_k\}$ is indeed just a permutation of that set." It makes sense, but since $\{r_1,\dots,r_k\}$ and $\{r_{k+1},\dots,r_n\}$ are not necessarily of the same size, why do you use $\mu$ twice in ${\rm sgn}(\mu(r_1,...,r_k)) \times {\rm sgn}(\mu (r_{k+1},...,r_n))$? $\endgroup$ Commented Apr 10, 2022 at 23:55
  • $\begingroup$ I think of $\mu$ as a perturbation of both sets and look at the restriction to each subset. In my example, $\mu(2,5)=(5,2)$ (odd permutation) and $\mu(1,3,4)=(4,1,3)$ (an even permutation). It makes sense to talk of the restriction of $\mu$ to each of these sets (since it only shuffles within each set). In contrast I don't have any clue of how to interpret e.g. $\rho(r_1,...,r_k)$ in the wikiproof page... $\endgroup$
    – H. H. Rugh
    Commented Apr 11, 2022 at 16:58
  • $\begingroup$ Basic question... Does 'perturbation' mean cycling the entries? I'm familiar with 'derangements' but that is the extent of my knowledge of the psychiatric labels used in combinatorics :-) $\endgroup$ Commented Apr 11, 2022 at 17:07
  • $\begingroup$ No perturbation is a typo. Read: 'permutation' $\endgroup$
    – H. H. Rugh
    Commented Apr 11, 2022 at 17:21
  • 1
    $\begingroup$ @JohnnyT. Yes, that is correct. $r$, $\mu$ and $\rho$ are all in $S_n$ $\endgroup$
    – H. H. Rugh
    Commented Apr 12, 2022 at 10:54

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .