# Trying to understand a proof of Laplace expansion

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

• It is much more clearly explained on Wikipedia once you get past the permutation cycle notation section: en.wikipedia.org/wiki/Laplace_expansion#Proof Commented Apr 3, 2022 at 17:05
• 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..... Commented Apr 4, 2022 at 12:08
• What special case? Commented Apr 4, 2022 at 13:15
• @JohnnyT. the proof on Wikipedia is for the general case $n \times n$. Commented Apr 6, 2022 at 18:30
• @AntoniParellada I have only just now truly seen what the question was asking. I now agree, it is different Commented Apr 7, 2022 at 7:08

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 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.
• "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))$? Commented Apr 10, 2022 at 23:55
• 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... Commented Apr 11, 2022 at 16:58
• @JohnnyT. Yes, that is correct. $r$, $\mu$ and $\rho$ are all in $S_n$ Commented Apr 12, 2022 at 10:54