\documentclass[12pt]{article}
\usepackage{e-jc}
\specs{P4.40}{21(4)}{2014}
\usepackage{amsmath,float}
\usepackage{amssymb}
\usepackage{stmaryrd}
\usepackage{amsthm}
\usepackage[singlelinecheck=false]{caption}

% use this command to create hyperlinks (optional and recommended)
\usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref}

% use these commands for typesetting doi and arXiv references in the bibliography
\newcommand{\doi}[1]{\href{http://dx.doi.org/#1}{\texttt{doi:#1}}}
\newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}}

% all overfull boxes must be fixed; 
% i.e. there must be no text protruding into the margins

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%  PSTricks-Packages:                                               %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Note: graphicx/color _after_ pstricks
\usepackage{pstricks}
\usepackage{multido}

%\usepackage{pst-node}   % for nodes
%\usepackage{pstcol}     % for 2e colors
%\usepackage{pst-grad}   % for fillstyle=gradient
%\usepackage{pst-char}   % for pscharpath
%\usepackage{pst-plot}   % for fileplot

% Note: graphicx/color _after_ pstricks

\usepackage{graphicx}
\usepackage{color}
%---------------------------------------------------------------

%----------- commands for pstricks grid-drawing ----------------
\newcommand{\showgrid}{}

% over-ride if \gridon
\newcommand{\gridon}{\renewcommand{\showgrid}{\psset{subgriddiv=1,griddots=10,gridlabels=6pt}\psgrid}}

\gridon % enable grid if uncommented

% put after each \begin{pspicture}
% \showgrid   % for use with \gridon macro - draws 1cm grid
%---------------------------------------------------------------

\newgray{hellgrau}{.89}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% General macros:                                                   %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\def\bit{\begin{itemize}}
\def\eit{\end{itemize}}
\def\beq{\begin{equation}}
\def\eeq{\end{equation}}

\def\BF#1{{\bf #1}}
\def\EM#1{{\em #1}}
\def\ID#1{\index{#1}}
\def\EMID#1{\EM{#1}\ID{#1}} % Weil das "\/" Probleme macht!
\def\figref#1{\ifenglish Figure\else Abbildung\fi~\ref{#1}}
\def\secref#1{\ifenglish Section\else Abschnitt\fi~\ref{#1}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Symbole fŸr spezielle Zahlmengen und Zahlen:                      %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\def\C{{\mathbb C}}
\def\E{{\mathbb E}}
\def\H{{\mathbb H}}
\def\N{{\mathbb N}}
\def\P{{\mathbb P}}
\def\Q{{\mathbb Q}}
\def\R{{\mathbb R}}
\def\Z{{\mathbb Z}}

\def\i{{\mathbf i}}
\def\d{{\mathrm d}}
\def\e{{\mathbf e}}
\def\1{{\mathbf 1}}
\def\0{{\mathbf 0}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Symbole fŸr Gleichungen und Definitionen:                         %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\def\defeq{:=}
\def\eqdef{=:}
\def\wrongeq{\stackrel{?}{=}}
\def\desiredeq{\stackrel{!?!}{=}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Makros fŸr Klammerungen:                                          %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\def\of#1{\left(#1\right)}
\def\absof#1{\left|#1\right|}
\def\setof#1{\left\{#1\right\}}
\def\subof#1{_{\left(#1\right)}}
\def\pas#1{\left(#1\right)}
\def\brk#1{\left[#1\right]}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Funktionen/Operatoren:                                            %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Signum einer reellen Zahl
\def\sgn{\operatorname{sgn}} 
% Varianz einer ZV
\def\var{{\operatorname{var}}}
% Kovarianz zweier ZV
\def\cov{{\operatorname{cov}}}
% Korrelation zweier ZV
\def\corr{{\operatorname{corr}}}
% Inneres Produkt zweier Vektoren
\def\ip#1#2{{\left\langle #1,#2\right\rangle}}
% NŠchsktleinere ganze Zahl
\def\floor#1{{\left\lfloor #1\right\rfloor}}
% NŠchstgrš§ere ganze Zahl
\def\ceil#1{{\left\lceil #1\right\rceil}}
% Falling factorials
\def\ffact#1#2{\pas{#1}_{#2}}
% Rising factorials
\def\rfact#1#2{\pas{#1}^{#2}}
% Faktorielle
\def\factorial#1{#1\,!}
% Konjugierte einer komplexen Zahl
\def\conjugate#1{\overline{#1}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%  Mengen:                                                          %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% AbkŸrzung fŸr {1,...,n}
\def\range#1{\left[#1\right]}  
% AbkŸrzung fŸr {alpha,...,omega}
\def\aorange#1#2{\left[#1,#2\right]}  
% Disjunkte Vereinigung von zwei Mengen
\def\disjuni{\,\dot{\cup}\,}
% Disjunkte Vereinigung von mehreren Mengen
\def\bigdisjuni{\dot{\bigcup}}
% KardinalitŠt
\def\card#1{\left\vert{#1}\right\vert}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%  Section-Nummern:                                                 %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\setcounter{secnumdepth}{10}
\setcounter{tocdepth}{2} % check this?

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%  LaTeX- Makros                                                    % 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newif\ifenglish
\englishtrue

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Theorem-environments                                              % 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Italic body:
\theoremstyle{plain}
\newtheorem{thm}{Theorem}
\newtheorem{pro}{Proposition}
\newtheorem{lem}{Lemma}
\newtheorem{cor}{Corollary}

\theoremstyle{definition}
\newtheorem{dfn}[thm]{Definition}

% Roman body:
\theoremstyle{remark}
\newtheorem{obs}[thm]{Observation}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Own Macros:                                                       % 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\def\secref#1{section~\ref{#1}}

% \def\pfaffian{{\mathrm{Pf}}}
\def\pfaffian{\operatorname{Pf}}
\def\hafnian{{\operatorname{Hf}}}
\def\per{\operatorname{per}}
\def\inv{\operatorname{inv}}
%
\def\matchings#1{{\mathcal M}_{#1}}
\def\superpositions#1{{\mathcal S}_{#1}}
\def\nofmatchings#1{M_{#1}}
\def\subgraph#1#2{\brk{#1-#2}}
\def\subgraphedges#1#2#3{\brk{#1-#2-#3}}
% \def\subgraph#1#2{G_{{\scriptscriptstyle-#2}}}
\def\weight{\omega}
\def\vertices{{\mathrm V}}
\def\edges{{\mathrm E}}
\def\orientation{\xi}
\def\symbolf{f\!}
\def\interlace{{\scriptstyle\rightleftarrows}}
\def\concat{{\scriptstyle\circ}}
\def\word#1{\pas{#1}}
\def\olperm#1{#1} % 1-line notation
\def\tlperm#1#2{\genfrac(){0pt}{0}{#2}{#1}} % 2-line notation
\def\complement#1{\overline{#1}}
\def\without{\!\setminus\!}
\def\symdef#1#2{#1\,{\vartriangle}\,#2} % symmetric difference
\def\numof#1{\#\of{#1}}                % number of a set
\def\cardof#1{\left\vert{#1}\right\vert}                % cardinality of a set
\def\smatch{\mu}                        % single matching
\def\bicoloured#1#2#3{#1_{{ #2}\vert{ #3}}}
\def\theblues{{\blue\mathbf{b}}}
\def\thereds{{\red\mathbf{r}}}
\def\thecoloureds{{\black\mathbf{c}}}
\def\thewhites{{\black\mathbf{w}}}
\def\swapcolours#1{\chi_{#1}}
% \def\setsum#1{{\scriptstyle\Sigma}#1}
\def\setsum#1{{{\mathbf\Sigma}\of{\!#1}}}
%\def\SETSUM#1#2{{{\mathbf\Sigma}_{#2}\of{\!#1}}}
\def\SETSUM#1#2{{{\mathbf\Sigma}\of{{#1\subseteq#2}}}}
\def\symm{\mathfrak{S}}
\def\descof#1{d\,\of{#1}}
\def\LHS{left--hand side}
\def\RHS{right--hand side}
\def\symmeven#1{{\symm^{0}_{#1}}}
\def\step#1{Step #1: }
\def\semibip#1#2{S_{#1,#2}}
\def\completeG#1{K_{#1}}
\def\completebip#1#2{K_{#1,#2}}
\def\word#1{{\mathbf #1}}
\def\pmatch{matching}
\def\Pmatch{Matching}
%\def\strangeset#1#2{{\mathcal F}\of{#1, #2, \thecoloureds}}
%\def\strangeset{{\mathcal F}\of{\therights, \thelefts, \thewhites\|X}}
\def\strangeset{{\mathcal F}\of{G\|X}}
\def\markextra#1{#1}
\def\disjuni{\,\dot{\cup}\,}
\def\bb{bb}
\def\rb{rb}
\def\br{br}
\def\rr{rr}
\def\and{\wedge}
\def\indexed#1#2{{{\mathbf #1}}_{#2}}
\def\redindexed#1{\setof{r: #1}}
\def\blueindexed#1{\setof{b: #1}}
\def\edgeindexed#1{\setof{e: #1}}
\def\complement#1{\overline{#1}}
%\def\thelefts{{\gray\bar{\mathbf R}}}
%\def\therights{{\gray\bar{\mathbf B}}}
\def\thelefts{{\red{\mathbf R}}}
\def\therights{{\blue{\mathbf B}}}
\def\myrange#1{\setof{1,\dots,k}}
\def\som{superposition of matchings}
\def\soms{superpositions of matchings}

\def\schurf{s}
\def\length#1{\ell\of{#1}}
\def\tableau{T}
\def\indexthis#1#2{{#1}^{(#2)}}
\def\sapadd#1#2#3{{#1}\!+^{#2}_{#3}}
\def\sappeel#1{\left.#1\right\downarrow}
\def\sappeeldown#1#2{\left.#1\right\downarrow^{#2}}
\def\sappeelup#1#2{\left.#1\right\uparrow_{(#2)}}
\def\cop{{\sl\bf cp}}
\def\coc{{\sl\bf cocp}}
\def\pointconf{configuration of (starting/ending) points (short: \cop){\gdef\pointconf{\cop}}}
\def\pointarr{circular orientation of coloured (starting/ending) points (short: \coc){\gdef\pointarr{\coc}}}

% Matrices and minors
\def\detwhole{{\mathbf m}}
\def\matminor#1#2#3{{#1}_{#2,#3}}
\def\matcominor#1#2#3{{#1}_{\overline{#2},\overline{#3}}}

\def\domain{\operatorname{domain}}
\def\image{\operatorname{image}}

\def\speciesname#1{\mathtt{#1}}

% Sum of elements in a set of integers
\def\sumset#1{{\scriptstyle\pas{\sum_{x\in #1}x}}}
\def\sumset#1#2{\Sigma_{#1\trianglelefteq#2}}
\def\signsumset#1#2{\sgn\of{#1\!\trianglelefteq\!#2}}

% Partial permutations
\def\concat{\star}
\def\complies{\subseteq}
\def\scheme#1{\brk{#1}}
\def\compat#1#2{{\mathbf #1}_{\brk{#2}}}

\def\complementoffirst#1#2{{\mathbf #1}_{#2}}

\def\lhs{\mathbf{lhs}}
\def\rhs{\mathbf{rhs}}

\title{\bf A combinatorial proof for Cayley's identity}

\author{Markus Fulmek\thanks{
Research supported by the National Research Network ``Analytic
Combinatorics and Probabilistic Number Theory'', funded by the
Austrian Science Foundation. 
}\\
\small Fakult\"at f\"ur Mathematik \\[-0.8ex]
\small Oskar-Morgenstern-Platz 1, A-1090 Wien, Austria \\
\small \tt Markus.Fulmek@Univie.Ac.At
}

\date{\dateline{Jul 15, 2014}{Nov 14, 2014}{Nov 27, 2014}\\
\small Mathematics Subject Classifications: 05A19}

\begin{document}

\maketitle

\begin{abstract}
In %\cite{Caracciolo:2013}, 
a recent paper, Caracciolo, Sokal and Sportiello presented, {\it inter alia},
an algebraic/combinatorial proof for Cayley's identity. The purpose of the present
paper is to give a ``purely
combinatorial'' proof for this identity; i.e., a proof involving only combinatorial arguments.
Since these arguments eventually employ
a generalization of Laplace's Theorem, we present a ``purely combinatorial'' proof for this theorem, too.
%\cite[section 148]{Muir:1933},
%for which
%a ``purely combinatorial'' proof is given in \cite[proof of Theorem 6]{Fulmek:2012}.
\end{abstract}

\section{Introduction}
\label{sec:intro}

For $n\in\N$, denote by $\range{n}$ the set $\setof{1,2,\dots,n}$ and let $X=X_n
%= \matminor{X}{\range{n}}{\range{n}} 
=\pas{x_{i,j}}_{\pas{i,j}\in\range{n}\times\range{n}}$
be an $n \times n$ matrix of indeterminates. For $I\subseteq\range{n}$ and $J\subseteq\range{n}$, we
denote
\bit
\item the \EM{submatrix} of $X$ corresponding to the rows $i\in I$ and the columns $j\in J$ by
$\matminor{X}{I}{J}$,
\item the \EM{complementary submatrix} of $\matminor X I J$ % in $X$
(which corresponds to the rows $i\in\overline{I}\defeq\range{n}\setminus I$ and the columns
$j\in\overline{J}\defeq\range{n}\setminus J$) by $\matcominor{X}{I}{J}$.
\eit

Let $M=\setof{x_1\leq x_2\leq\dots\leq x_m}$ be a finite ordered
set, and let $S=\setof{x_{i_1},\dots, x_{i_k}}\subseteq M$ be a subset of $M$. We define
$$\signsumset{S}{M}\defeq\pas{-1}^{\sum_{j=1}^k i_j}.$$

As pointed out in \cite[Section 2.6]{Caracciolo:2013}, the following identity is
conventionally but erroneously attributed to % Arthur 
Cayley. (Muir
\cite[vol. 4, p. 479]{Muir:1906} attributes this identity to Vivanti \cite{Vivanti:1890}.)
\begin{thm}[Cayley's Identity]
\label{thm:cayley}
Consider $X = \pas{x_{i,j}}_{\pas{i,j}\in\range{n}\times\range{n}}$, and let
$\partial = \pas{\frac{\partial}{\partial x_{i,j}}}$ be the corresponding
$n \times n$ matrix of partial derivatives\footnote{$\partial$ is also known as \EM{Cayley's $\Omega$--process}.}.
Let $I,J\subseteq\range{n}$ with $\card{I}=\card{J}=k$. Then we have for $s\in\N$:
\begin{multline}
\label{eq:cayley}
\det\of{\matminor{\partial}{I}{J}}\pas{\det\of X}^s = \\
%\sgn\of{I,J}
s\cdot\pas{s+1}\cdots\pas{s+k-1}\cdot\pas{\det\of X}^{s-1}\cdot
\signsumset{I}{\range n}\cdot\signsumset{J}{\range n}
\cdot\det\of{\matcominor{X}{I}{J}}.
\end{multline}
\end{thm}
By the alternating property of the determinant, Cayley's Identity is
in fact equivalent to the following special case of \eqref{eq:cayley}.

\begin{cor}[Vivanti's Theorem]
\label{cor:vivanti}
Specialize $I=J=\range{k}$ for some $k\leq n$ in Theorem~\ref{thm:cayley}.
Then we have for $s\in\N$:
\begin{multline}
\label{eq:vivanti}
\det\of{\matminor{\partial}{\range{k}}{\range{k}}}\pas{\det\of X}^s
=
s\cdot\pas{s+1}\cdots\pas{s+k-1}\cdot\pas{\det\of X}^{s-1}\cdot\det\of{\matcominor{X}{\range k}{\range k}}.
\end{multline}
\end{cor}

\section{Combinatorial proof of Vivanti's Theorem}
We may \EM{view} the % expansion of the
determinant of $X$
as the \EM{generating function} of all permutations $\pi$ in $\symm_n$,
where the (signed) weight of a permutation $\pi$ is given as
$\weight\of\pi\defeq\sgn\pi\cdot\prod_{i=1}^nx_{i,\pi\of i}$:
$$
\det\of X =\sum_{\pi\in \symm_n}\weight\of\pi. %\sgn{\pi}\cdot\prod_{i=1}^nx_{i,\pi\of i}.
$$
\subsection{View permutations as perfect matchings}
\label{sec:perm-match}
For our considerations, it is convenient to \EM{view} a permutation
$\pi\in\symm_n$ as a \EM{perfect matching} $m_\pi$ of the complete bipartite graph $K_{n,n}$,
where the vertices consist of two copies of $\range{n}$ which are arranged in their natural order;
see \figref{fig:permmatch} for an illustration of this simple idea: In the picture,
we show the
\EM{domain} of $\pi$ as \EM{lower} vertices and the
\EM{image} of $\pi$ as \EM{upper} vertices.
It is easy to see that the edges of such perfect matching can be drawn
in a way such that all \EM{intersections} are of precisely two (and not more)
edges, and that the number of these intersections equals the number of
\EM{inversions} of $\pi$, whence the sign  of $\pi$ is
$$
\sgn\of\pi=\pas{-1}^{\numof{\text{intersections in }m_\pi}}.
$$
This simple visualization of permutations and their inversions is already used in \cite[\S 15, p.32]{Aitken:1956}: We call it the \EM{permutation diagram}.
% ``Aitken-diagram of permutation $\pi$'').
So assigning weight $x_{i,j}$ to the edge pointing from lower vertex $i$ to 
upper vertex $j$ and defining the
weight $\weight\of{m_\pi}$ of the permutation diagram $m_\pi$ % corresponding to $\pi$
to be the product of the edges belonging to $m_\pi$, we may write
$$
\weight\of\pi=\pas{-1}^{\numof{\text{intersections in }m_\pi}}\cdot\weight\of{m_\pi}.
$$

\begin{figure}[H]
\begin{center}
\input{graphics/permmatch}
\caption{\label{fig:permmatch} 
View the permutation $\pi=\olperm{2 5 1 4 3}$ as the corresponding perfect matching
$m_\pi$ in the complete bipartite graph $K_{5,5}$.The intersections of edges
are indicated by small circles; they correspond bijectively to $\pi$'s inversions:
$$\displaystyle \numof{\text{inversions of }\pi}=\card{\setof{(1,3),(2,3),(2,4),(2,5),(4,5)}}=5.$$
Assigning weight $x_{i,j}$ to the edge pointing from lower vertex $i$ to 
upper vertex $j$ gives the
contribution of the permutation $\pi$ to the determinant of $X_5$:
$$\weight\of\pi = \pas{-1}^5\cdot x_{1,2}\cdot x_{2,5}\cdot x_{3,1}\cdot x_{4,4}\cdot x_{5,3}.$$
}
\end{center}
\end{figure}

\vspace*{-3ex}
Given this view, the combinatorial interpretation of the $s$-th power of the determinant $\det\of X$ is
obvious: It is the generating function of all $s$-tuples $m=\pas{m_{\pi_1},\dots,m_{\pi_s}}$
of permutation diagrams, where the (signed) weight of such $s$-tuple $m$ is given as
$$
\weight\of m=\prod_{i=1}^s\pas{-1}^{\numof{\text{intersections in }m_{\pi_i}}}\cdot\weight\of{m_{\pi_i}}.
$$

\begin{figure}[H]
\begin{center}
\input graphics/det2s
\caption{\label{fig:det2s} Objects counted by the generating function of a power of a determinant.
For $n=5$, the picture shows a typical object of weight
$$
%\scriptstyle
\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!
+
x_{1,1}%\cdot 
x_{1,2}^2%\cdot 
x_{1,4}%\cdot
x_{2,3}%\cdot 
x_{2,4}%\cdot 
x_{2,5}^2%\cdot
x_{3,1}%\cdot 
x_{3,3}%\cdot 
x_{3,4}%\cdot 
x_{3,5}%\cdot
x_{4,1}%\cdot 
x_{4,3}%\cdot 
x_{4,4}%\cdot 
x_{4,5}%\cdot
x_{5,1}%\cdot 
x_{5,2}^2%\cdot 
x_{5,3},
$$
which is counted by the generating function $\det\of{X}^4$.
(The edge connecting lower vertex $3$ to upper vertex $3$ in the $4$--th (right--most) matching
is drawn as zigzag-line, just to avoid
intersections of more than two edges in a single point.)
}
\end{center}
\end{figure}

\subsection{Action of the determinant of partial derivatives}
Next we need to describe combinatorially the \EM{action} of the determinant $\det\of{\matminor{\partial}{\range{k}}{\range{k}}}$
of partial derivatives. Let $m=\pas{m_{\pi_1},\dots,m_{\pi_s}}$ be an $s$-tuple of permutation diagrams
counted in the generating function $\pas{\det\of X}^s$, and let $\tau\in\symm_k$:
Then the summand
$$
\partial_\tau\defeq\sgn\of\tau\cdot\prod_{i=1}^k\frac{\partial}{\partial x_{i,\tau\of i}}
$$
applied to $\weight\of m$ yields
$$
\sgn\of\tau\cdot\pas{\prod_{i=1}^k\frac{\partial}{\partial x_{i,\tau\of i}}}\weight\of m =
\sgn\of\tau\cdot c_{\tau,m}\cdot \frac{\weight\of m}{\prod_{i=1}^k{x_{i,\tau\of i}}},
$$
where $c_{\tau,m}$ is the number of ways to \EM{choose} the set of $k$ edges
$\setof{\pas{i\to\tau\of i}:i\in\range{k}}$ from \EM{all} the edges in $m$ (this number, of course,
might be zero). We may visualize the action of $\delta_\tau$ as ``erasing the edges constituting $\tau$
in $m$''; see \figref{fig:derivdet2s} for an illustration.

\begin{figure}[H]
\begin{center}
\input graphics/derivdet2s
\caption{\label{fig:derivdet2s}
Let $n=5$, $s=4$ and $k=3$ in Corollary~\ref{cor:vivanti}. The picture shows % the 
four possible ways of ``erasing'' the edges constituting
$\tau\in\symm_3$ from the $4$-tuple $\pas{m_{\pi_1},m_{\pi_2},m_{\pi_3},m_{\pi_4}}$ of
matchings, where $\pas{\pi_1,\pi_2,\pi_3,\pi_4}\in\symm_5^4$ is
$\pas{\olperm{3 1 2 5 4},\olperm{5 1 3 2 4},\olperm{1 4 2 5 3},\olperm{2 3 4 1 5}}$. The erased edges are shown as
grey dashed lines.
}
\end{center}
\end{figure}

Hence we have:
\begin{equation}
\label{eq:partialaction}
\det\of{\matminor{\partial}{\range{k}}{\range{k}}}\pas{\det\of X}^s
=
\sum_{m\in\symm_n^s}\!\!\weight\of m
\sum_{\tau\in\symm_k}c_{\tau,m}\cdot\frac{\sgn\of\tau }{\prod_{i=1}^k{x_{i,\tau\of i}}}.
\end{equation}
\subsection{Double counting} For our purposes, it is convenient to interchange
the summation in \eqref{eq:partialaction}. This application of \EM{double counting} amounts
here to a simple change of view: Instead of counting the ways to \EM{choose} the set of edges corresponding
to $\tau$ from all the edges corresponding to some \EM{fixed} $s$-tuple $m$, we
fix $\tau$ and consider the set of $m$'s from which $\tau$'s edges might be chosen. 
This will involve two considerations:
\bit
\item In how many ways can the edges corresponding to $\tau$ be \EM{distributed} on
	$s$ copies of the bipartite graph $K_{n,n}$?
\item For each such distribution, what is the set of compatible $s$-tuples of permutation diagrams?
\eit
For example, if $k=3$ and $s=4$ (as in \figref{fig:derivdet2s}), there clearly
\bit
\item is $1$ way to distribute the three edges on a \EM{single} copy of the $4$ bipartite
	graphs (see the fourth row of pictures in \figref{fig:derivdet2s}), and there are $4$ ways to
	choose such single copy,
\item are $3$ ways to distribute the three edges on \EM{precisely two} copies of the $4$ bipartite
	graphs (see the second and third row of pictures in \figref{fig:derivdet2s}), and there are $4\cdot 3$
	ways to choose such pair of copies (whose order is relevant),
\item is $1$ way to distribute the three edges on \EM{precisely three} copies of the $4$ bipartite
	graphs (see the first row of pictures in \figref{fig:derivdet2s}), and there are $4\cdot 3 \cdot 2$
	ways to choose such triple of copies (whose order is relevant).
\eit

\subsection{Partitioned permutations}
A distribution of the edges corresponding to $\tau\in\symm_k$ on $s$ copies of the
bipartite graph $K_{n,n}$ may be viewed (see \figref{fig:derivdet2s})
\bit
\item as an $s$-tuple of \EM{matchings} (some of which may be empty; to stress the
fact that these matchings are \EM{not} perfect, we also call them \EM{partial}
matchings) of $K_{k,k}$
\item such that the union of these $s$
\EM{partial} matchings gives the \EM{perfect matching} $m_\tau$ of  $K_{k,k}$.
\eit
Clearly, to each such partial matching corresponds a \EM{partial permutation} $\tau_i$, which
we may write in two-line notation as follows:
\bit
\item the lower line shows the \EM{domain} of $\tau_i$ in its natural order,
\item the upper line shows the \EM{image} of $\tau_i$,
\item the \EM{ordering} of the upper line represents the permutation $\tau_i$.
\eit
We say that each of these $\tau_i$ is a \EM{partial permutation} of $\tau$, and that
$\tau$ is a \EM{partitioned permutation}. We write in short:
$$
\tau =\tau_1\concat\tau_2\concat\dots\concat\tau_s.
$$
%permutation in the lower line and its \EM{image} in the upper line; the ordering of the upper
%line representing the permutation
%.
For example, the rows of pictures  in \figref{fig:derivdet2s} correspond to the 
partitioned permutations
% $4$-tuples of partial permutations 
(written in the aforementioned two-line notation)
% to $4$-tuples of partial permutations:
\bit
\item ${\binom{3}{1}\concat\binom{1}{2}\concat\binom{2}{3}\concat\binom{}{}}$ for the first row,
\item ${\binom{3\, 2}{1\, 3}\concat\binom{1}{2}\concat\binom{}{}\concat\binom{}{}}$ for the second row,
\item ${\binom{3\, 1}{1\, 2}\concat\binom{}{}\concat\binom{2}{3}\concat\binom{}{}}$ for the third row,
\item ${\binom{3\, 1\, 2}{1\, 2\, 3}\concat\binom{}{}\concat\binom{}{}\concat\binom{}{}}$ for the fourth row.
\eit

\subsection{Equivalence relation for partitioned permutations}
\label{sec:equivalence}
For any partitioned permutation $\tau=\tau_1\concat\tau_2\concat\dots\concat\tau_s$,
consider the $s$-tuple of the \EM{upper rows} (in the aforementioned two-line notation) \EM{only}:
We call this $s$-tuple of \EM{permutation words} the \EM{partition scheme} of $\tau$ and denote it
by $\scheme{\tau}$. We say that $\tau=\tau_1\concat\tau_2\concat\dots\concat\tau_s$
\EM{complies} to its partition scheme $\scheme{\tau}=\scheme{\tau_1\concat\tau_2\concat\dots\concat\tau_s}$
and denote this by ${\tau}\complies{\scheme{\tau_1\concat\tau_2\concat\dots\concat\tau_s}}$.

Now consider the following equivalence relation on the set of partitioned permutations:
$$
\mu={\mu_1\concat\dots\concat\mu_s}\sim\nu={\nu_1\concat\dots\concat\nu_s}:\iff\scheme{\mu}=\scheme{\nu}.
$$
%i.e., $\image\of{\mu_i}=\image\of{\nu_i}$ for $i=1,\dots, s$. We call such $s$-tuple of upper rows
%(in two-line notation) partitioned permutation, where
%the bottom row of the two-line notation is 
By definition, the corresponding equivalence classes are \EM{indexed} by a partition scheme,
and $\mu=\mu_1\concat\mu_2\concat\dots\concat\mu_s$ belongs to the equivalence class
of  $\tau=\tau_1\concat\tau_2\concat\dots\concat\tau_s$ iff $\mu\complies\scheme{\tau}$.
(For $s>1$, a partitioned permutation $\tau$ is \EM{not}
uniquely determined by $\scheme{\tau}$.)

It is elementary to determine the \EM{number} of these equivalence classes: Think of filling in
\EM{successively}
the entries $1,2,\dots,k$ into the partition scheme $\scheme{\tau_1\concat\tau_2\concat\dots\concat\tau_s}$.
Starting with the empty scheme $\scheme{\concat\dots\concat\concat}$, we find $s$ possibilities
to fill in $1$, giving $\scheme{\concat\dots\concat1\concat\dots\concat}$. Now there are $s+1$
possibilities to fill in $2$, etc.:
%
%In the language of
%\EM{combinatorial species} (see, for instance, \cite{Bergeron-Labelle-Leroux:1998}) the $s$-tuples
%of permutation
%words indexing these
%classes correspond bijectively to the (labelled) species $\pas{\speciesname{Permutations}}^s$, and since the
%exponential generating function of $\speciesname{Permutations}$ is
%$$
%\sum_{n=0}^\infty n!\cdot\frac{z^n}{n!}= \frac1{1-z},
%$$
%the
%exponential generating function of $\pas{\speciesname{Permutations}}^s$ is simply
%$$
%\pas{\frac1{1-z}}^s = \pas{1-z}^{-s}=\sum_{k=0}^\infty\binom{-s}{k}\pas{-1}^k z^k=
%\sum_{k=0}^\infty s\cdot\pas{s+1}\cdots\pas{s+k-1} \frac{z^k}{k!}.
%$$
So the number of these equivalence classes is $s\cdot\pas{s+1}\cdots\pas{s+k-1}$, which
is precisely the factor in \eqref{eq:vivanti}. Our proof will be complete if we manage
to show that the generating
functions of \EM{each} of these equivalence classes are the \EM{same}, namely
$$ \pas{\det\of X}^{s-1}\cdot\det\of{\matcominor{X}{I}{J}}.$$

\subsection{Accounting for the signs}
A necessary first step for this task is to investigate how the sign of a
permutation $\pi$ is changed by \EM{removing} a given partial permutation $\pi_1$:
We view this as \EM{erasing} all the edges belonging to $\pi_1$'s permutation diagram
$m_{\pi_1}$ from $\pi$'s permutation diagram $m_\pi$; see again \figref{fig:derivdet2s}.

\begin{lem}
\label{cor:remove-edges}
Let $\pi\in\symm_n$ be a partitioned permutation $\pi=\pi_1\concat\pi_2$, where $\pi_1$ is the partial permutation
$$
\pi_1 =
\begin{pmatrix}\pi\of{i_1} & \pi\of{i_2} & \cdots & \pi\of{i_k} \\ {i_1} & {i_2} & \cdots & {i_k}\end{pmatrix}
$$
(with $\setof{i_1\leq i_2\leq\cdots\leq i_k}\subseteq\range{n}$). Clearly,
$\pi_2$ is the permutation
corresponding to the matching $m_\pi$ with edges $\pas{i_1,\pi\of{i_1}},\pas{i_2,\pi\of{i_2}},\dots,\pas{i_k,\pi\of{i_k}}$ erased, which we also denote by $\pi\setminus\pi_1$. Then we have
$$
\sgn\of\pi = \pas{-1}^{\sum_{j=1}^k\pi\of{i_k} -i_k}\cdot\sgn\of{\pi_1}\cdot\sgn\of{\pi_2}.
$$
If we denote $I=\setof{i_1,\dots,i_k}$ and $J=\setof{\pi\of{i_1}, \dots, \pi\of{i_k}}$, we may
rewrite this as
\begin{equation}
\label{eq:remove-edges}
\sgn\of\pi = \signsumset{I}{\range n}\cdot\signsumset{J}{\range n}\cdot\sgn\of{\pi_1}\cdot\sgn\of{\pi\setminus\pi_1}.
\end{equation}
\end{lem}
\begin{proof}\noindent
View the permutation diagram $m_\pi$ of $\pi=\pi_1\concat\pi_2$ as a \EM{bicoloured}
perfect matching of $K_{n,n}$, where the edges and vertices corresponding
to $\pi_1$ are coloured green and the edges and vertices corresponding
to $\pi_2$ are  coloured red (see \figref{fig:innerouter}). Clearly,
\bit
\item the set $I$ is the set of (the labels of the) \EM{lower} green vertices,
\item the set $J$ is the set of (the labels of the) \EM{upper} green vertices.
\eit

\begin{figure}[H]
\begin{center}
\input{graphics/innerouter}
\vspace*{-2ex}
\caption{
%View partitioned permutations as bicoloured permutation diagrams. 
The \EM{bicoloured} permutation diagram $m_\pi$ corresponding to the partitioned permutation $\pi=\pi_1\concat\pi_2$, where
$$
\pi_1=\tlperm{2 4 5 7 8}{5 2 7 6 9}
\text{ and }
\pi_2=\tlperm{1 3 6 9}{3 1 4 8}.
$$
The edges corresponding to $\pi_1$ are shown as green (solid) lines, the
edges corresponding to $\pi_2$ are shown as red (dotted) lines. The \EM{inactive
intersections} (of green/red edges) are indicated by small white circles,
the other intersections (of green/green or red/red edges) are indicated by
small black circles.
\label{fig:innerouter}}
\end{center}
\end{figure}


Note that the intersections in $m_\pi$ come in three flavours:
\bit
\item intersections of two green edges (which are accounted for in $\sgn\of{\pi_1}$),
\item intersections of two red edges (which are accounted for in $\sgn\of{\pi_2}$),
\item intersections of a green and a red edge: Since they do not contribute to the
	signs, let us call them the \EM{inactive intersections}.
\eit
We will prove \eqref{eq:remove-edges} by showing the following two statements:
\bit
\item[1.] The parity of the number of inactive intersections depends \EM{only} on the sets
	$I$ and $J$, i.e., on the \EM{positions} of the (lower and upper) green vertices.
\item[2.] The number of inactive intersections equals
	$\sum_{j=1}^k\absof{\pi\of{i_j}-i_j}$ (which, of course, is
	equal to
	$\sum_{j=1}^k\pi\of{i_j}+\sum_{j=1}^k i_j$ modulo $2$)
	in the case that $\pi_1:I\to J$ and
	$\pi_2:\pas{\range{n}\setminus I}\to\pas{\range{n}\setminus J}$ are the
	unique \EM{order--preserving} bijections (i.e, there are \EM{only}
	inactive intersections; see \figref{fig:innerouter2}).
\eit


For the first statement, consider two edges $e_1$ and $e_2$
of the \EM{same} colour, where
$e_1=\pas{a,d}$ and $e_2=\pas{b,c}$
connect lower vertices $a$ and $b$ with upper vertices
$d$ and $c$, respectively, and look at the effect of replacing these edges
by $e_1^\prime=\pas{a,c}$ and $e_2^\prime=\pas{b,d}$: It is
easy to see that an edge $e$ of the \EM{other} colour 
\bit
\item has an \EM{even} number of intersections with $e_1$
	and $e_2$ (i.e., intersects neither of them or both of them)
	if and only if it has an \EM{even} number of intersections
	with $e_1^\prime$ and $e_2^\prime$,
\item has an \EM{odd} number of intersections with $e_1$
	and $e_2$ (i.e., intersects exactly one of them)
	if and only if it has an \EM{odd} number of intersections
	with $e_1^\prime$ and $e_2^\prime$.
\eit
See \figref{fig:lemma1} for an illustration: Note that replacing
edges $e_1,e_2$ by $e_1^\prime,e_2^\prime$ corresponds to multiplying $\pi_1$ with
the transposition $\pas{c,d}$, and by multiplying with a sequence of appropriate transpositions,
we can remove all inversions from $\pi_1$ and $\pi_2$; and this operation does
not change
the parity of the number of inactive intersections.

\begin{figure}[H]
\begin{center}
\input{graphics/lemma1}
\vspace*{-2ex}
\caption{The left picture shows the green edges (shown as solid lines)
$e_1=\pas{a,d}$ and
$e_2=\pas{b,c}$, which are replaced by the green edges $e_1^\prime=\pas{a,c}$
and $e_2^\prime=\pas{b,d}$ in the right picture: Observe that for
every red edge $e$ (shown as dotted line) the \EM{parities} of the numbers
of intersections with $\setof{e_1,e_2}$ and $\setof{e_1^\prime,e_2^\prime}$
are the same. (Some edges are drawn as curved lines here for graphical reasons.)
\label{fig:lemma1}}
\end{center}
\end{figure}

For the second statement, simply have a look at \figref{fig:innerouter2} and
observe that in the case where neither $\pi_1$ nor $\pi_2$ have inversions,
$\absof{\pi\of{i_j}-i_j}$ is the number of intersections
of the $j$--the green edge with red edges.
\end{proof}

\begin{figure}[H]
\begin{center}
\input{graphics/innerouter2}
\caption{Partitioned permutation $\pi^\prime=\pi_1^\prime\concat\pi_2^\prime$, where both
$\pi_1^\prime$ and $\pi_2^\prime$ have no inversions; i.e., there are only
\EM{inactive} intersections in the bicoloured permutation diagram
$m_{\pi_1^\prime\concat\pi_2^\prime}$.\label{fig:innerouter2}}
\end{center}
\end{figure}


\subsection{Sums of (signed) products of minors}
Now consider a fixed equivalence class in the sense of \secref{sec:equivalence}, which is
indexed by a \EM{partition-scheme}
$$
\scheme{\tau_1\concat\tau_2\concat\cdots\concat\tau_s}.
$$
We want to compute the generating function $G_{\scheme{\tau}}$ of this equivalence class: Clearly, we may
concentrate on the \EM{nonempty} partial permutations; so w.l.o.g. we have to consider
the partition-scheme
$$
\scheme{\tau_1\concat\tau_2\concat\cdots\concat\tau_m}
$$
which consists only of \EM{nonempty} partial permutations $\tau_j$ for $1\leq j\leq m\leq s$.
For any $\sigma\in\symm_k$ with
$\sigma\complies\scheme{\tau_1\concat\tau_2\concat\cdots\concat\tau_m}$, such
partition scheme corresponds to a unique \EM{ordered partition} of the image of $\sigma$:
$$
\image\of\sigma=\range{k}=
\pas{\image\of{\tau_1}}\disjuni\pas{\image\of{\tau_2}}\disjuni\cdots\disjuni\pas{\image\of{\tau_m}}=J_1\disjuni J_2\disjuni\cdots\disjuni J_m,
$$
and any specification of a \EM{compatible ordered partition} $\compat{I}{J}=\pas{I_1,I_2,\dots,I_m}$, i.e.,
$$
\range{k}=I_1\disjuni I_2\disjuni\cdots\disjuni I_m\text{ where }\card{I_l}=\card{J_l},l=1,\dots,m,
$$
uniquely determines such $\sigma$, which we denote by $\sigma\of{\compat{I}{J},\scheme{\tau}}$.

Equation~\eqref{eq:remove-edges} gives the sign-change
caused by erasing the edges corresponding to $\tau_l$ (with respect to \EM{any} permutation in $\symm_n$
which contains $\tau_l$ as a partial permutation), whence we can write 
the generating function as
\begin{multline*}
G_{\scheme{\tau}} = \det\of X^{s-m} \\
\times
\sum_{\compat{I}{J}}
\sgn\of{\sigma\of{\compat{I}{J},\scheme{\tau}}}\cdot
\prod_{l=1}^m\pas{\sgn\of{\tau_l}\cdot
\signsumset{I_l}{\range{n}}\cdot\signsumset{J_l}{\range{n}}\cdot\det\of{\matcominor{X}{I_l}{J_l}}},
\end{multline*}
where the sum is over all compatible partitions $\compat{I}{J}$.
(The factor $\sgn\of{\sigma\of{\compat{I}{J},\scheme{\tau}}}$ comes from the \EM{determinant}
of partial derivatives.)
Clearly,
$$
\pas{\prod_{l=1}^m\signsumset{I_l}{\range{n}}}\cdot\pas{\prod_{l=1}^m\signsumset{J_l}{\range{n}}}=1,
$$
so it remains to show that
\begin{equation}
\label{eq:showthis}
\sum_{\compat{I}{J}}
\sgn{\sigma\of{\compat{I}{J},\scheme{\tau}}}\cdot
\prod_{l=1}^m\pas{\sgn\of{\tau_l}\cdot\det\of{\matcominor{X}{I_l}{J_l}}}
=
\det\of{X}^{m-1}\det\of{\matcominor{X}{\range k}{\range k}}.
\end{equation}
This, of course, is true for $m=1$. We proceed by induction on $m$.

For any ordered partition $S_1\disjuni S_2\disjuni\dots\disjuni S_m = \range{k}$,
we introduce the shorthand notation
$$\complementoffirst{S}{l}\defeq\range{k}\setminus\pas{S_1\disjuni S_2\disjuni\dots\disjuni S_l}.$$
%Set ${\mathbf I}_l\defeq\range{k}\setminus\bigcup_{j=1}^l I_j$ and ${\mathbf J}_l\defeq\range{k}\setminus\bigcup_{j=1}^l J_j$.
Moreover, write $d_{I_j}\defeq\det\of{\matcominor{X}{I_j}{J_j}}$ for short. Then the lefthand-side
of \eqref{eq:showthis}
may be written as the $\pas{m-1}$-fold sum
\begin{equation}
\label{eq:multisum}
\sum_{\substack{I_1\subseteq\complementoffirst{I}{0}\\\card{I_1}=\card{J_1}}}\sgn\of{\tau_1}d_{I_1}
\!\!
\sum_{\substack{I_2\subseteq\complementoffirst{I}{1}\\\card{I_2}=\card{J_2}}}\sgn\of{\tau_2}d_{I_2}
\cdots
\!\!\!\!\!\!
\sum_{\substack{I_{m-1}\subseteq\complementoffirst{I}{m-2}\\\card{I_{m-1}}=\card{J_{m-1}}}}
\!\!\!\!\!\!
\sgn\of{\tau_{m-1}}d_{I_{m-1}}
\sgn\of{\tau_m}d_{I_m}\cdot\,\sgn\of{\sigma},
\end{equation}
where $I_m=\complementoffirst{I}{m-2}\setminus I_{m-1}$ and $\sigma=\sigma\of{\compat{I}{J},\scheme{\tau}}$.

\def\strich#1{#1^\prime}

Assume $\complementoffirst{J}{m-2}=\setof{j_1\leq\dots\leq j_a}$,
$\complementoffirst{I}{m-2}=\setof{i_1\leq\dots\leq i_a}$ and $J_m=\setof{j_{s_1}\leq\cdots\leq j_{s_b}}$.
Then the special choice $\strich{I_m}=\setof{i_{s_1}\leq\cdots\leq i_{s_b}}$ (i.e., with
respect to the relative ordering, ``$\strich{I_m}$ is the same subset as $J_m$ '')
and $\strich{I_{m-1}}=\complementoffirst{I}{m-2}\setminus \strich{I_m}$
determines \EM{uniquely} a partial permutation $\strich{\tau_{m-1}}$
% of $\sigma\of{\compat{I}{J},\scheme{\tau}}$
$$
\strich{\tau_{m-1}}:\complementoffirst{I}{m-2}\to\complementoffirst{J}{m-2}.
$$
According to \eqref{eq:remove-edges}, by construction we have
\begin{equation}
\label{eq:aux}
\sgn\of{\strich{\tau_{m-1}}}=\sgn\of{\tau_{m-1}}\cdot\sgn\of{\tau_m}.
\end{equation}
Now consider $\sigma=\sigma\of{\compat{I}{J},\scheme{\tau}}$ in the innermost sum of
\eqref{eq:multisum}:
\EM{Erasing} the edges corresponding to $\tau_{m-1}$ and $\tau_{m-2}$ from $m_\sigma$ and
\EM{replacing} them by the edges corresponding to $\strich{\tau_{m-1}}$ yields a permutation
$\strich{\sigma}=\tau_1\concat\cdots\tau_{m-2}\concat\strich{\tau_{m-1}}$
(which, of course, complies to the partition scheme $\scheme{\strich{\tau}}=\scheme{\tau_1\concat\cdots\tau_{m-2}\concat\strich{\tau_{m-1}}}$).
Since by \eqref{eq:remove-edges} together with \eqref{eq:aux} we have
$$
\sgn\of{\strich{\tau_{m-1}}} = \sgn\of{\tau_{m-1}\concat\tau_m}\cdot\signsumset{{I_m}}{\complementoffirst{I}{m-2}}\cdot\signsumset{J_m}{\complementoffirst{J}{m-2}}
$$
and (clearly)
$$
\sigma\setminus\pas{\tau_{m-1}\concat\tau_m}=\strich{\sigma}\setminus\strich{\tau_{m-1}},
$$
we also have (again by \eqref{eq:remove-edges})
$$
\sgn\of\sigma=\signsumset{{I_m}}{\complementoffirst{I}{m-2}}\cdot\signsumset{J_m}{\complementoffirst{J}{m-2}}\cdot\sgn\of{\strich{\sigma}}.
$$
%
%Now look at the innermost sum:
%$\overline{\tau}\defeq\tau_{m-1}\concat\tau_m$ is a partial permutation of $\sigma$,
%$$
%\overline{\tau}:\complementoffirst{I}{m-2}\to\complementoffirst{J}{m-2}.
%$$
%
%%Let $X=\setof{x_1,\dots,x_m}\subset\Z$ be an ordered
%%set, and let $S=\setof{x_{i_1},\dots,x_{i_k}}$, $k\leq m$, be a subset. In this
%%situation, we define
%%$$\sumset{S}{X}\defeq\sum_{j=1}^k i_j.$$
%
%By \eqref{eq:remove-edges},
%we have $\sgn\of{\overline{\tau}}=\sgn\of{\tau_{m-1}}\cdot\sgn\of{\tau_m}\cdot\signsumset{I_m}{\complementoffirst{I}{m-2}}\cdot\signsumset{J_m}{\complementoffirst{J}{m-2}}$.
Hence the innermost sum of \eqref{eq:multisum} can be written as
$$
\sgn\of{\strich{\tau_{m-1}}}\cdot
\pas{
% \sum_{I_{m-1}\subseteq\complementoffirst{I}{m-2}}
\sum_{\substack{I_{m-1}\subseteq\complementoffirst{I}{m-2}\\\card{I_{m-1}}=\card{J_{m-1}}}}
\!\!\!\!\!\!
\signsumset{I_m}{\complementoffirst{I}{m-2}}\cdot\signsumset{J_m}{\complementoffirst{J}{m-2}}
\cdot d_{I_{m-1}}
\cdot d_{I_m}
}\cdot\sgn\of{\strich\sigma}.$$
If we can show that this last sum equals
$\det\of X\cdot \det\of{\matcominor{X}{\complementoffirst{I}{m-2}}{\complementoffirst{J}{m-2}}}$, then
\eqref{eq:showthis} follows by induction, since the $\pas{m-1}$--fold sum in \eqref{eq:multisum}
thus reduces to
an $\pas{m-2}$--fold sum, which corresponds to the partition-scheme $\scheme{\strich{\tau}}=\scheme{\tau_1\concat\tau_2\concat\dots,\tau_{m-2}\concat\strich{\tau_{m-1}}}$.
\subsection{(A generalization of) Laplace's theorem}
Luckily, 
%
%Careful
%accounting for the signs leads to an (iterated) application of Laplace's Theorem.
%
%Let $X=\setof{x_1,\dots,x_m}\subset\Z$ be an ordered
%set, and let $S=\setof{x_{i_1},\dots,x_{i_k}}$, $k\leq m$, be a subset. In this
%situation, we define
%$$\sumset{S}{X}\defeq\sum_{j=1}^k i_j.$$
%
%\begin{thm}[Laplace's Theorem]
%\label{thm:Laplace}
%Let $a=\pas{a_{i,j}}_{(i,j)\in\range{m}\times\range{m}}$ be an $m\times m$-matrix.
%Consider some fixed set $I\subseteq\range{m}$.
%Then we have
%\begin{equation}
%\label{eq:laplace-general}
%\det\of{a} = %\pas{-1}^{\setsum{\range{m}}}\cdot
%\sum_{\substack{J\subseteq\range{m},\\\cardof{J}=\cardof{I}}}
%\sgn\of{I,J}\cdot
%\det{\matminor{a}{I}{J}}.
%\end{equation}
%\end{thm}
a generalization (see \cite[section 148]{Muir:1933}) of Laplace's Theorem
serves as the closer for our argumentation:
\begin{thm}
\label{thm:muir148}
Let $X$ be an $\pas{m+k}\times\pas{m+ k}$-matrix, and let
$1\leq i_1<i_2<\cdots<i_m\leq m+k$ and
$1\leq j_1<j_2<\cdots<j_m\leq m+k$ be (the indices of) $k$ fixed rows and
$k$ fixed columns of $X$. Denote the set of these (indices of) rows and columns by $R$ and $C$,
respectively.
%and set $A\defeq\setof{j_1,\dots,j_k}$ and 
%$O\defeq\setof{j_{k+1},\dots,j_{2\cdot k}}$. Let $A^\prime\defeq\range{m+2\cdot k}\setminus A$
%and $O^\prime\defeq\range{m+2\cdot k}\setminus O$.
% Let 
%respectively, of $a$. 
Consider some fixed % list $1\leq r_1<r_2<\cdots<r_k\leq m$
subset $I\subseteq R$.
Then we have:
\begin{equation}
\label{eq:muir148}
\det\of{X}\cdot\det\of{\matcominor{X}{R}{C}} = %\pas{-1}^{\setsum{\range{m}}}\cdot
\sum_{\substack{J\subseteq C,\\\card{J}=\card{I}}}
{\signsumset{I}{R}\cdot\signsumset{J}{C}}\cdot
\det\of{\matminor{X}{\overline{R\setminus I}}{\overline{C\setminus J}}}
\cdot
\det\of{\matminor{X}{\overline{I}}{\overline{J}}}
.
\end{equation}
\end{thm}
A combinatorial
proof for this identity (using an interpretation of determinants as
non--intersecting lattice paths) is implicit in
\cite[proof of Theorem 6]{Fulmek:2012}, but we shall give a
combinatorial argument which employs the ideas presented in this paper.
%\secref{sec:perm-match}.
%A combinatorial
%proof for this identity is given in \cite[proof of Theorem 6]{Fulmek:2012}, but in order
%to make our presentation 
\def\ueberschrift#1{{\bf #1:} }
\begin{proof}\noindent
Denote by $\lhs$ ($\rhs$) the set of signed and weighted objects corresponding to the left--hand side (right--hand side)
of \eqref{eq:muir148}. We will prove \eqref{eq:muir148} by showing
\bit
\item that there is a weight--preserving and sign--preserving
	\EM{injection} $\phi:\lhs\to\rhs$,
\item and that there is as weight--preserving but sign--reversing
	\EM{involution} $\psi$ on the set $\rhs\setminus\phi\of\lhs$.
\eit

\ueberschrift{Overlays of green/red (partial) matchings}
In the same sense as presented in \secref{sec:perm-match}, we may
view both $\lhs$ and $\rhs$ as families of
\EM{pairs} of matchings $\pas{m_\pi,m_\sigma}$, where
we may draw the first matching $m_\pi$ (with green edges) upon the second one
$m_\sigma$ (with red edges),
so that the pairs appear as \EM{overlays} of green and red matchings.


\figref{fig:matching-overlay}, which serves as running example in our proof,
shows such overlay of matchings belonging to $\lhs$ for
$m=5$, $k=4$, $R=\setof{2,3,6,8,9}$ and $C=\setof{1,2,5,6,8}$ (whence $\overline{R}=
\range{9}\setminus R=\setof{1,4,5,7}$ and $\overline{C}=\range{9}\setminus C=\setof{3,4,7,9}$).
More precisely, the picture shows the permutation diagrams $m_\pi$ and $m_\sigma$
corresponding to the pair of partial permutations $\pas{\pi,\sigma}$,
where (in $2$--line notation)
$$\pi=\tlperm{1 2 3 4 5 6 7 8 9}{1 4 2 7 3 5 6 9 8}\text{ and } \sigma = \tlperm{1 4 5 7}{3 7 9 4}.$$
The green edges belonging to $m_\pi$ are shown as solid lines, and the
red edges belonging to $m_\sigma$ are shown as dotted lines.

\begin{figure}[H]
\begin{center}
\input{graphics/matching-overlay}
\vspace*{-2ex}
\caption{%Illustration for the proof of Theorem~\ref{thm:muir148}:
Terms in the
expansion of the product of determinants may be viewed as ``overlays'' of the
permutation diagrams of two partial permutations. The red (dotted) edge connecting
lower vertex 4 to upper vertex 7 is drawn as curved line for graphical reasons
only. The active intersections of edges are indicated by small circles.
\label{fig:matching-overlay}
}
\end{center}
\end{figure}


This pair $\pas{\pi,\sigma}$ corresponds to the term
$$
\pas{-1}^6
\cdot
\pas{
x_{1,1}x_{2,4}x_{3,2}x_{4,7}x_{5,3}x_{6,5}x_{7,6}x_{8,9}x_{9,8}
}
\cdot
\pas{-1}^2
\cdot
\pas{
x_{1,3}x_{4,7}x_{5,9}x_{7,4}
},
$$
which occurs in the expansion of the product of the minors
$$
\det\of{X}\cdot\det\of{\matcominor{X}{R}{C}}
$$
for $X=\pas{x_{i,j}}_{i,j=1}^{9}$.
Obviously,
the \EM{lower vertices} correspond to the \EM{rows} of $X$, while the
\EM{upper vertices} correspond to the \EM{columns} of $X$ in \figref{fig:matching-overlay}.

Note that for an overlay of matchings, an intersection of two edges does only contribute to the
sign if the edges are of the \EM{same} colour (both red or both green): We call such intersections
\EM{active}; all other intersections (of edges of different colours) are called \EM{inactive}
(recall \secref{sec:perm-match}). 

\ueberschrift{Green, red and uncoloured vertices}
%
In every overlay of matchings in $\lhs\cup\rhs$, all \EM{upper} vertices labelled with numbers
from the set $\overline{C}$ and all \EM{lower} vertices labelled with numbers
from the set $\overline{R}$ are incident with a red edge \EM{and} with a green edge:
We call these the \EM{uncoloured} vertices. All the other vertices
are incident with precisely one (either green or red) edge: We assign to them
the colour of this single incident edge and call them the \EM{coloured}
(i.e., either green or red) vertices. (All coloured vertices are green in
\figref{fig:matching-overlay}.)

\ueberschrift{Bicoloured paths}

Obviously, an overlay of matchings constitutes a bipartite graph (with double edges
allowed). The \EM{connected components} of this bipartite graph  are either
double edges (one green and one red, see the edges connecting lower vertex $4$ to
upper vertex $7$ in \figref{fig:matching-overlay}) or \EM{paths}
\bit
\item whose endpoints are \EM{coloured} points,
\item and whose edges \EM{alternate} in colour.
\eit
We call these components \EM{bicoloured paths}: \figref{fig:matching-bicoloured-paths}
shows the two bicoloured paths connecting the lower vertices labelled $3$ and 
$8$ with the upper vertices labelled $2$ and $1$, respectively, in
our running example. 

\begin{figure}[H]
\begin{center}
\input{graphics/matching-bicoloured-paths}
\vspace*{-2ex}
\caption{Bicoloured paths (drawn here as thick gray lines) starting in lower vertices 
$3$ and $8$ (see the running example in \figref{fig:matching-overlay}).
\label{fig:matching-bicoloured-paths}}
\end{center}
\end{figure}


Obviously, if a bicoloured path connects vertices $x$ and $y$, then
\bit
\item $x$ and $y$ are on \EM{different} levels (i.e., one lower and one upper vertex) 
	if and only if $x$ and $y$ have the \EM{same} colour,
\item $x$ and $y$ have \EM{different} colours (i.e., one green and one red vertex)
	if and only if $x$ and $y$ are on the \EM{same} level.
\eit

\ueberschrift{Swapping of colours in bicoloured paths}
%
Observe that for any overlay of matchings, the \EM{swapping} of the colours
(red and green) for all edges in some bicoloured path $p$ simply yields another
overlay of matchings \EM{with the same absolute weight} (since only the \EM{colour}
of edges and vertices does change) and with the same set of uncoloured vertices:
We call this operation the \EM{swapping of colours in the bicoloured path $p$}.
(\figref{fig:matching-overlay-recoloured}
shows the effect of swapping colours in both bicoloured paths from
\figref{fig:matching-bicoloured-paths}: Observe that now there are also
red vertices.)

Note that a bicoloured path $p$ might have ``inner intersections'' (i.e., $p$ may contain
intersecting edges), but the swapping of colours in $p$ does not change the status (active or
inactive) of such ``inner intersections''. On the other hand, for \EM{every} ``outer intersection''
(of some edge $e_1$ belonging to $p$ with some edge $e_2$ belonging to \EM{another} bicoloured path),
the status is changed (from active to inactive and vice versa) by swapping colours. So swapping
colours in $p$ effects a sign change $\pas{-1}^k$, where $k$ is the number of intersections of
(edges of) $p$ with (edges of) \EM{other} bicoloured paths.

\ueberschrift{The injection $\phi$}
%
For $\pas{m_\pi,m_\sigma}\in\lhs$, we define $\phi\of{m_\pi,m_\sigma}$ by swapping colours in \EM{all} (distinct!) bicoloured paths
starting in the lower vertices labelled by the numbers from $I\subseteq R$.
It is easy to see that $\phi$ is an \EM{injective} mapping $\lhs\to\rhs$ (in fact,
it is an involution $\lhs\to\phi\of\lhs$) which preserves (absolute)
weights.
 
In our running example, choose $I=\setof{3,8}$: \figref{fig:matching-overlay-recoloured}
shows the result of swapping colours in the bicoloured paths shown in
\figref{fig:matching-bicoloured-paths}. The \EM{lower} vertices with labels in $I$ are now
\EM{red}, and the subset of labels of \EM{upper} red vertices is $J=\setof{1,2}$. The overlay
of matchings $\pas{m_{\pi^\prime},m_{\sigma^\prime}}$ corresponds to the partial
permutations
%(in $2$--line notation)
$$\pi^\prime=\tlperm{1 2 4 5 6 7 9}{3 4 7 9 5 6 8}\text{ and } \sigma^\prime = \tlperm{1 3 4 5 7 8}{1 2 7 3 4 9},$$
which correspond to the term
$$
\pas{-1}^5
\cdot
\pas{
x_{1,3}x_{2,4}x_{4,7}x_{5,9}x_{6,5}x_{7,6}x_{9,8}
}
\cdot
\pas{-1}^2
\cdot
\pas{
x_{1,1}x_{3,2}x_{4,7}x_{5,3}x_{7,4}x_{8,9}
}
$$
occuring in the expansion of the product of the minors
$$
\det\of{\matminor{X}{\overline{R\setminus I}}{\overline{C\setminus J}}}
\cdot
\det\of{\matminor{X}{\overline{I}}{\overline{J}}}.
$$

\begin{figure}[H]
\begin{center}
\input{graphics/matching-overlay-recoloured}
\vspace*{-2ex}
\caption{Overlay of matchings obtained by swapping colours in the bicoloured paths
(see \figref{fig:matching-bicoloured-paths}) starting in lower vertices  $3$ and $8$
(see the running example in \figref{fig:matching-overlay}).
\label{fig:matching-overlay-recoloured}}
\end{center}
\end{figure}

\ueberschrift{The mapping $\phi$ is not injective, so we really need the involution $\psi$}
%
So far we found an injection $\phi:\lhs\to\rhs$ which preserves \EM{absolute}
weights: We need to show yet
\bit
\item that the change of sign effected by $\phi$ equals
	${\signsumset{I}{R}\cdot\signsumset{J}{C}}$,
\item and that the total weight of $\rhs\setminus\phi\of{\lhs}$ equals $0$.
\eit

\figref{fig:mor-involution} demonstrates that (in general) $\phi$ is not surjective
(whence $\rhs\setminus\phi\of{\lhs}\neq\emptyset$): The overlay
of matchings $\pas{m_{\pi^{\prime\prime}},m_{\sigma^{\prime\prime}}}$ depicted
there corresponds to the partial permutations 
%(in $2$--line notation)
$$\pi^{\prime\prime}=\tlperm{1 2 4 5 6 7 9}{5 3 4 6 7 8 9}\text{ and } 
\sigma^{\prime\prime} = \tlperm{1 3 4 5 7 8}{1 2 3 4 7 9},$$
which correspond to the term
$$
\pas{-1}^2
\cdot
\pas{
x_{1,5}x_{2,3}x_{4,4}x_{5,6}x_{6,7}x_{7,8}x_{9,9}
}
\cdot
\pas{-1}^0
\cdot
\pas{
x_{1,1}x_{3,2}x_{4,3}x_{5,4}x_{7,7}x_{8,9}
}
$$
\EM{also} occuring in the expansion of the product of the minors
$$
\det\of{\matminor{X}{\overline{R\setminus I}}{\overline{C\setminus J}}}
\cdot
\det\of{\matminor{X}{\overline{I}}{\overline{J}}},
$$
but \EM{not} occurring as $\phi\of z$ for any $z\in\lhs$, 
% the reason obviously being the 
since there is a bicoloured
path starting in the upper vertex with label $1$, which also \EM{ends} in an upper
vertex (with label $5$): This cannot happen in overlays belonging to $\lhs$.
It is easy to see that \EM{every} element of $\rhs\setminus\phi\of{\lhs}$
contains a bicoloured path starting \EM{and} ending in upper vertices, so the
involution $\psi$ suggests itself: Identify the leftmost upper vertex which is
connected to another upper vertex by a bicoloured path $p$, and swap colours in $p$.
This clearly defines an involution preserving \EM{absolute} weights: It remains
to show that $\psi$ is \EM{sign--reversing}, so that the total weight of
$\rhs\setminus\phi\of{\lhs}$ equals $0$.

\begin{figure}[H]
\begin{center}
\input graphics/mor-involution
\caption{An overlay of two matchings belonging to $\rhs$ which does not belong
to $\phi\of\lhs$.
\label{fig:mor-involution}}
\end{center}
\end{figure}


\ueberschrift{Sign changes effected by swapping colours in bicoloured paths}
%
Bicoloured paths are \EM{connections} of coloured points, which
we may simply indicate by \EM{corresponding edges}
(see Figures~\ref{fig:matching-bicoloured-connections} and
\ref{fig:matching-bicoloured-connections2}). Observe that
	two such edges corresponding to (different) bicoloured paths $p_1$ and $p_2$ have an
	intersection if and only if $p_1$ and $p_2$
	have an \EM{odd} number of intersections, and
recall that swapping the colours in some bicoloured path $p$ yields a 
sign change of $\pas{-1}^k$, where $k$ is the number of ``outer intersections'' of $p$
(i.e., intersections with \EM{other} bicoloured paths).

If we \EM{forget} the uncoloured points
in \figref{fig:matching-bicoloured-connections},
we recognize a permutation diagram: It is clear that for \EM{every} overlay of matchings from
$\lhs$, we obtain such permutation diagram.

\begin{figure}[H]
\begin{center}
\input{graphics/matching-bicoloured-connections}\\[-2ex]
\caption{The edges corresponding to the connections by bicoloured paths in \figref{fig:matching-overlay}.
\label{fig:matching-bicoloured-connections}}
\end{center}
\end{figure}

Denote by $B$ the set of \EM{all} bicoloured paths in an overlay of matchings from
$\lhs$ and consider some \EM{subset}
$S\subset B$ and its complement 
$\overline{S}=B\setminus S$.
By swapping colours of \EM{all} bicoloured paths in 
$S$, the status (active/inactive) of every ``inner intersection'' of $S$
(i.e., an intersection of some $p\in S$ with another $p^\prime\in S$, where $p=p^\prime$ is possible)
is \EM{unchanged}, while the status of every ``outer intersection'' of $S$ 
(i.e., an intersection of some path $p\in S$ with some path $q\in\overline{S}$) is swapped (from active
to inactive and vice versa): So the sign change equals $\pas{-1}^k$, where $k$ is the number
of ``outer intersections'' of $S$. But this is the \EM{same} sign change we encounter if we
partition the permutation corresponding to $B$ into the two partial permutations corresponding
to $S$ and $\overline{S}$, respectively, in the sense of Lemma~\ref{cor:remove-edges}:
So by \eqref{eq:remove-edges}, this sign
equals ${\signsumset{I}{R}\cdot\signsumset{J}{C}}$, and the injection $\phi$ is sign--preserving.

\begin{figure}[H]
\begin{center}
\input{graphics/matching-bicoloured-connections2}\\[-2ex]
\caption{The edges corresponding to the connections by bicoloured paths in \figref{fig:mor-involution}.
\label{fig:matching-bicoloured-connections2}}
\end{center}
\end{figure}

By the same reasoning, we see that the sign change effected by swapping
some bicoloured path connecting two \EM{upper} vertices $x$ and $y$
(see \figref{fig:upper-connection})
is $\pas{-1}^k$, where $k$ is the number of coloured vertices lying \EM{between}
$x$ and $y$. Assuming that $x$ is the $i$--th and $y$ is the $\pas{i+k+1}$--the element
of the ordered set $C$ (which is the set of upper coloured vertices), such swapping replaces factor $\pas{-1}^i$ by $\pas{-1}^{i+k+1}$ (or
vice versa) in $\signsumset{J}{C}$, which gives sign change $\pas{-1}^{k+1}$:
Altogether, such swapping yields sign change $\pas{-1}^{2k+1}=-1$,
whence the involution $\psi$ is sign--reversing.
\end{proof}

\begin{figure}[H]
\begin{center}
\input{graphics/upper-connection}\\[-3ex]
\caption{An edge corresponding to a connection between two \EM{upper} vertices.
\label{fig:upper-connection}}
\end{center}
\end{figure}

\subsection*{Acknowledgement}
I thank the anonymous referee for a very careful reading of the manuscript and helpful comments
and suggestions.

%\bibliographystyle{plain}
%\bibliography{paper}

\begin{thebibliography}{1}

\bibitem{Aitken:1956}
A.C. Aitken.
\newblock {\em Determinants and Matrices}.
\newblock Oliver \& Boyd, Ltd., Edinburgh, 9th. edition, 1956.

\bibitem{Caracciolo:2013}
S.~Caracciolo, A.D. Sokal, and A.~Sportiello.
\newblock Algebraic/combinatorial proofs of {C}ayley-type identities for
  derivatives of determinants and pfaffians.
\newblock {\em Advances in Applied Mathematics}, 50(4):474 -- 594, 2013.

\bibitem{Fulmek:2012}
M.~Fulmek.
\newblock Viewing determinants as nonintersecting lattice paths yields
  classical determinantal identities bijectively.
\newblock {\em Electron. J. Combin.}, 19(3):\#P21, 2012.

\bibitem{Muir:1906}
T.~Muir.
\newblock {\em The Theory of Determinants in the historical order of
  development}.
\newblock MacMillan and Co., Limited, London, 1906--1923.

\bibitem{Muir:1933}
T.~Muir.
\newblock {\em A Treatise on the Theory of Determinants}.
\newblock Longmans, Green and Co., London, 1933.

\bibitem{Vivanti:1890}
G.~Vivanti.
\newblock Alcune formole relative all'operazione {$\Omega$}.
\newblock {\em Rend. Circ. Mat. Palermo}, 1890.

\end{thebibliography}


\end{document}
