5
$\begingroup$

I am looking for a proof for the following conjecture. I think the result follows from applying a generalization of the Cauchy-Binet formula to the matrix $\mathbf{M}$ defined bellow. I've tested it as much as I could using Mathematica and am convinced it is true, but I haven't been able to prove it. Any help will be much appreciated.


Setup

Suppose $\mathbf{A}$ and $\mathbf{B}$ are $(n \times m)$ and $(m \times n)$ matrices respectively, with $n<m$ and $\operatorname{rank}(\mathbf{A})=\operatorname{rank}(\mathbf{B})=n$.

Let $K \equiv \{1,\dots,m\}$, $\mathbf{X}_{k}$ denote the matrix $\mathbf{X}$ keeping only columns and rows in $k$, $\mathbf{X}_{rk}$ denote the matrix $\mathbf{X}$ keeping only rows in $k$, and $\mathbf{X}_{ck}$ denote the matrix $\mathbf{X}$ keeping only columns in $k$. Also, for any $k \subset K$, let $K_n$ be the set of subsets of $K$ with $n$ elements.

Then, using the Cauchy-Binet formula, the determinant of the matrix $\mathbf{A}\mathbf{B}$, denoted by $\Delta$, can be written as

$$\Delta \equiv \det(\mathbf{A}\mathbf{B}) = \sum_{k\in K_n}{\det(\mathbf{A}_{ck})\det(\mathbf{B}_{rk})}. $$

Denote each element of this sum by

$$ d_k \equiv \det(\mathbf{A}_{ck})\det(\mathbf{B}_{rk}), \;\;\;\;\text{for all }k \in K_n.$$

Consider the matrix $\mathbf{M}$ given by

$$ \mathbf{M} = \mathbf{B}(\mathbf{A}\mathbf{B})^{-1}\mathbf{A}, $$

with principal minors given by $\det(\mathbf{M}_{k})$ for any $k \in P(K)$, where $P(K)$ is the power set of $K$ (the set of all subsets of $K$).


Conjecture

I want to show that $$ \det(\mathbf{M}_{k}) = \frac{1}{\Delta}\sum_{j\in \{ i \in K_n : k \subset i \}}d_j, \;\;\;\;\text{for all }k \in P(K) $$


Example to clarify notation

Suppose that $m=3$ and $n=2$. Then, from the definitions we have that

\begin{align} P(K) =& \{\{1\},\{2\},\{3\},\{1,2\},\{1,3\},\{2,3\},\{1,2,3\}\} \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; \\[3ex] K_n =& \{\{1,2\},\{1,3\},\{2,3\}\} \\[3ex] \mathbf{A} =& \left[\begin{matrix} a_{11} & a_{12} & a_{13} \\ a_{21} & a_{22} & a_{23} \end{matrix}\right], \;\;\; \mathbf{B} = \left[\begin{matrix} b_{11} & b_{12} \\ b_{21} & b_{22} \\ b_{31} & b_{32} \end{matrix}\right] \\[3ex] \mathbf{A}\mathbf{B} =& \left[\begin{matrix} a_{11}b_{11}+a_{12}b_{21}+a_{13}b_{31} & a_{11}b_{12}+a_{12}b_{22}+a_{13}b_{32} \\ a_{21}b_{11}+a_{22}b_{21}+a_{23}b_{31} & a_{21}b_{12}+a_{22}b_{22}+a_{23}b_{32}\end{matrix}\right] \end{align}

and the Cauchy-Binet formula implies

\begin{align} \det(\mathbf{A}\mathbf{B}) =& \det(\mathbf{A}_{c\{1,2\}})\det(\mathbf{B}_{r\{1,2\}}) + \det(\mathbf{A}_{c\{1,3\}})\det(\mathbf{B}_{r\{1,3\}}) + \det(\mathbf{A}_{c\{2,3\}})\det(\mathbf{B}_{r\{2,3\}}) \\[2ex] =& \det\left[\begin{matrix} a_{11} & a_{12} \\ a_{21} & a_{22} \end{matrix}\right]\det\left[\begin{matrix} b_{11} & b_{12} \\ b_{21} & b_{22} \end{matrix}\right] + \det\left[\begin{matrix} a_{11} & a_{13} \\ a_{21} & a_{23} \end{matrix}\right]\det\left[\begin{matrix} b_{11} & b_{12} \\ b_{31} & b_{32} \end{matrix}\right] + \\[1ex] & \det\left[\begin{matrix} a_{12} & a_{13} \\ a_{22} & a_{23} \end{matrix}\right]\det\left[\begin{matrix} b_{21} & b_{22} \\ b_{31} & b_{32} \end{matrix}\right]. \end{align}

Again, using the definitions above we have that

\begin{align} d_{\{1,2\}} \equiv & \; \det(\mathbf{A}_{c\{1,2\}})\det(\mathbf{B}_{r\{1,2\}}) \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\\[1ex] d_{\{1,3\}} \equiv & \; \det(\mathbf{A}_{c\{1,3\}})\det(\mathbf{B}_{r\{1,3\}}) \\[1ex] d_{\{2,3\}} \equiv & \; \det(\mathbf{A}_{c\{2,3\}})\det(\mathbf{B}_{r\{2,3\}}) \\[3ex] \Delta \equiv & \; d_{\{1,2\}}+d_{\{1,3\}}+d_{\{2,3\}} \end{align}

and, with some algebra, it is easy to verify that the principal minors of $\mathbf{M}$ can be written as

\begin{align} \det(\mathbf{M}_{\{1,2\}}) =& \; \frac{1}{\Delta}\sum_{j\in \{1,2\}}d_j =\; \frac{1}{\Delta}d_{\{1,2\}} \\[2ex] \det(\mathbf{M}_{\{1,3\}}) =& \; \frac{1}{\Delta}\sum_{j\in \{1,3\}}d_j =\; \frac{1}{\Delta}d_{\{1,3\}} \\[2ex] \det(\mathbf{M}_{\{2,3\}}) =& \; \frac{1}{\Delta}\sum_{j\in \{2,3\}}d_j =\; \frac{1}{\Delta}d_{\{2,3\}} \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; \\[2ex] \det(\mathbf{M}_{\{3\}}) =& \; \frac{1}{\Delta}\sum_{j\in \{\{1,3\},\{2,3\}\}}d_j =\; \frac{1}{\Delta}(d_{\{1,3\}}+d_{\{2,3\}}) \\[2ex] \det(\mathbf{M}_{\{2\}}) =& \; \frac{1}{\Delta}\sum_{j\in \{\{1,2\},\{2,3\}\}}d_j =\; \frac{1}{\Delta}(d_{\{1,2\}}+d_{\{2,3\}}) \\[2ex] \det(\mathbf{M}_{\{1\}}) =& \; \frac{1}{\Delta}\sum_{j\in \{\{1,2\},\{1,3\}\}}d_j =\; \frac{1}{\Delta}(d_{\{1,2\}}+d_{\{1,3\}}) \end{align}

Moreover, $\det(\mathbf{M}_{\{1,2,3\}}) =0$ follows from the fact that $\det(\mathbf{M}_{\{1,2,3\}})$ is a principal minor of order $3>2=n$. All principal minors of $\mathbf{M}$ of order greater than $n$, are equal to zero, since $\operatorname{rank}(\mathbf{M})=n$.


Attempts at the proof using the suggestions by @darijgrinberg

Fix $k \in P(K)$ and let $v\equiv |k|$, i.e. the number of elements in $k$. First suppose that $v \gt n$, so that $\det(\mathbf{M}_k)=0$, since $\operatorname{rank}(\mathbf{M}_k)=0$, and $\{ i \in K_n : k \subset i \} = \emptyset$, so that the conjecture holds trivially.

Next, suppose that $v \le n$. What follows is tentative.


Working with the definition of $\mathbf{M}_{k}$:

By definition,

$$ \mathbf{M}_{k}=\mathbf{B}_{rk}(\mathbf{A}\mathbf{B})^{-1}\mathbf{A}_{ck} $$

where $\mathbf{B}_{rk}$ and $(\mathbf{A}\mathbf{B})^{-1}\mathbf{A}_{ck}$ are $(v \times n)$ and $(n \times v)$ matrices respectively. Let $L\equiv \{1,\dots,n\}$ and $L_v$ be the set of subsets of $L$ with $v$ elements, and from the Cauchy-Binet formula we have that

$$ \det(\mathbf{M}_{k})=\sum_{j \in L_v}\det\left(\mathbf{B}_{rk,cj}\right)\det\left((\mathbf{A}\mathbf{B})_{rj}^{-1}\mathbf{A}_{ck}\right), \tag1$$

and

$$ \det\left((\mathbf{A}\mathbf{B})_{rj}^{-1}\mathbf{A}_{ck}\right)=\sum_{i \in L_v}\det\left((\mathbf{A}\mathbf{B})_{rj,ci}^{-1}\right)\det\left(\mathbf{A}_{ri,ck}\right).$$

So that

$$ \det(\mathbf{M}_{k})=\sum_{i,j \in L_v}\det\left((\mathbf{A}\mathbf{B})_{rj,ci}^{-1}\right)\det\left(\mathbf{A}_{ri,ck}\right)\det\left(\mathbf{B}_{rk,cj}\right),$$

and since

$$ (\mathbf{A}\mathbf{B})^{-1}=\frac{1}{\Delta}\operatorname{adj}(\mathbf{A}\mathbf{B}) \implies (\mathbf{A}\mathbf{B})_{rj,ci}^{-1}=\frac{1}{\Delta}\operatorname{adj}(\mathbf{A}\mathbf{B})_{rj,ci} $$

it follows that

$$ \det(\mathbf{M}_{k})=\frac{1}{\Delta^v} \sum_{i,j \in L_v}\det\left(\operatorname{adj}(\mathbf{A}\mathbf{B})_{rj,ci}\right)\det\left(\mathbf{A}_{ri,ck}\right)\det\left(\mathbf{B}_{rk,cj}\right).$$

Next, for each $i,j \in L_{v}$ define $i'\equiv \{1,\dots,n\}\setminus i$ and $j'\equiv \{1,\dots,n\}\setminus j$, then it follows from Jacobi's theorem that

$$ \det(\operatorname{adj}(\mathbf{A}\mathbf{B})_{rj,ci})=(-1)^{\sigma_{ij}}\det(((\mathbf{A}\mathbf{B})^{\top})_{rj',ci'})\Delta^{v-1}=(-1)^{\sigma_{ij}}\det(\mathbf{A}_{rj'}\mathbf{B}_{ci'}) $$

where

$$ \sigma_{ij} \equiv i_{v+1}'+\cdots+i_{n}'+j_{v+1}'+\cdots+j_{n}' $$

and, therefore,

$$ \det(\mathbf{M}_{k})=\frac{1}{\Delta}\sum_{i,j \in L_{v}}(-1)^{\sigma_{ij}}\det(\mathbf{A}_{rj'}\mathbf{B}_{ci'})\det(\mathbf{A}_{ri,ck})\det(\mathbf{B}_{rk,cj}) $$

So far I haven't been able to proceed from here.


Working with the conjecture equation:

Notice that for any $j \in K_{n}$,

$$ \det((\mathbf{A}\mathbf{B})^{-1}\mathbf{A}_{cj})=\frac{1}{\Delta}\det(\mathbf{A}_{cj}), $$

so that the conjecture can be rewritten as

$$ \det(\mathbf{M}_{k}) = \sum_{j\in \{ i \in K_n : k \subset i \}}\det(\mathbf{B}_{rj})\det((\mathbf{A}\mathbf{B})^{-1}\mathbf{A}_{cj}), \tag2$$

which looks similar equation $(1)$, rewritten here for convenience

$$ \det(\mathbf{M}_{k})=\sum_{j \in L_v}\det\left(\mathbf{B}_{rk,cj}\right)\det\left((\mathbf{A}\mathbf{B})_{rj}^{-1}\mathbf{A}_{ck}\right). $$

I am not sure how to deal with the difference in the indexes between the two equations. My guess is that I will need to use a Laplace expansion to equation $(2)$.

$\endgroup$
  • $\begingroup$ @darijgrinberg Thank you! $\endgroup$ – mzp Apr 19 '16 at 3:18
  • $\begingroup$ OK, I think I know how this works, but I'm not sure when I'll have time to write up the details. (Sorry for not using your boldsymbol notations; too much to type.) For every subset $k$ of $\left\{1,2,\ldots,m\right\}$, let $B\succ k$ be the matrix obtained from $B$ by keeping only the rows indexed by the elements of $k$. Let $k\prec A$ be the matrix obtained from $A$ by keeping only the columns indexed by the elements of $k$. Let $C = \left(AB\right)^{-1}$. Then, $M_k = \left(k \prec A\right) C \left(B \succ k\right)$ (easy). Thus, you can compute $\det M_k$ using Cauchy-Binet, e.g. by ... $\endgroup$ – darij grinberg Apr 19 '16 at 3:32
  • $\begingroup$ ... splitting $ \left(k \prec A\right) C \left(B \succ k\right)$ as $ \left(k \prec A\right) \left(C \left(B \succ k\right)\right)$. The second factor will be a column-minor of $C \left(B \succ k\right)$ of size $k$; you can move the $\det C = \Delta^{-1}$ out of it. I think the rest shouldn't be difficult. $\endgroup$ – darij grinberg Apr 19 '16 at 3:34
  • $\begingroup$ Actually, our notations disagree: My $M_k$ is your $\mathsymbol{M}_{\text{complement of }k}$. Sorry. I think my notations are better, since my $P\left(k\right)$ then consists of $n$-element subsets, not of $m-n$-element subsets. $\endgroup$ – darij grinberg Apr 19 '16 at 3:35
  • $\begingroup$ @darijgrinberg This is great! I can kind of see how it will work out now. Fell free to use your notation if you choose to write this up as an answer, I agree that it is more intuitive :). (I changed $P(k)$ to $F(k)$ to avoid confusion with the power set of $k$). $\endgroup$ – mzp Apr 19 '16 at 3:46
2
+50
$\begingroup$

So, I think I have a proof now. It is nowhere as simple as I believed when I wrote the comments.

I shall use a few relatively standard facts without much of a proof; I hope you know them (if not, let me know and I'll expand).

First, let me introduce my notations (which are sometimes different from yours): Fix a commutative ring $\mathbf{k}$. Let $\mathbb{N}=\left\{ 0,1,2,\ldots\right\} $. For each $n\in\mathbb{N}$, let $\left[ n\right] $ denote the $n$-element set $\left\{ 1,2,\ldots,n\right\} $. For each $n\in\mathbb{N}$, let $I_{n}\in\mathbf{k}^{n\times n}$ be the $n\times n$ identity matrix. For each $n\in\mathbb{N}$ and each $\left( a_{1} ,a_{2},\ldots,a_{n}\right) \in\mathbf{k}^{n}$, let $\operatorname*{diag} \left( a_{1},a_{2},\ldots,a_{n}\right) \in\mathbf{k}^{n\times n}$ be the diagonal $n\times n$-matrix whose diagonal entries are $a_{1},a_{2} ,\ldots,a_{n}$. I shall use the standard abbreviation $\sum\limits_{U\subseteq V}$ (when $V$ is a set) for $\sum\limits_{U\in\mathcal{P}\left( V\right) }$ (where $\mathcal{P}\left( V\right) $ denotes the power set of $V$). For any $n\in\mathbb{N}$ and $m\in\mathbb{N}$ and any $n\times m$-matrix $A\in\mathbf{k}^{n\times m}$, we define the following submatrices of $A$:

  • If $S=\left\{ s_{1}<s_{2}<\cdots<s_{k}\right\} $ is a subset of $\left[ n\right] $, then $A_{rS}$ denotes the $k\times m$-matrix whose rows are the rows numbered $s_{1},s_{2},\ldots,s_{k}$ of $A$ (in this order).

  • If $T=\left\{ t_{1}<t_{2}<\cdots<t_{\ell}\right\} $ is a subset of $\left[ m\right] $, then $A_{cT}$ denotes the $n\times\ell$-matrix whose columns are the columns numbered $t_{1},t_{2},\ldots,t_{\ell}$ of $A$ (in this order).

  • If $S=\left\{ s_{1}<s_{2}<\cdots<s_{k}\right\} $ is a subset of $\left[ n\right] $ and if $T=\left\{ t_{1}<t_{2}<\cdots<t_{\ell}\right\} $ is a subset of $\left[ m\right] $, then $A_{rS,cT}$ denotes the $k\times\ell $-matrix $\left( a_{s_{i},t_{j}}\right) _{1\leq i\leq k,\ 1\leq j\leq\ell}$, where $A$ is written in the form $\left( a_{i,j}\right) _{1\leq i\leq n,\ 1\leq j\leq m}$. Equivalently, $A_{rS,cT}=\left( A_{rS}\right) _{cT}=\left( A_{cT}\right) _{rS}$.

Let me start with the standard facts that I will be using:

Proposition 1. Let $n\in\mathbb{N}$ and $A\in\mathbf{k}^{n\times n}$. Then, \begin{equation} \det\left( I_{n}+A\right) =\sum\limits_{G\subseteq\left[ n\right] } \det\left( A_{rG,cG}\right) . \end{equation}

Actually, Proposition 1 is a particular case of the following more general (and probably better known) fact:

Proposition 1'. Let $n \in \mathbb{N}$, $A \in \mathbf{k}^{n \times n}$ and $x \in \mathbf{k}$. Then, \begin{equation} \det\left( xI_{n}+A\right) = \sum\limits_{G\subseteq\left[ n\right] } \det\left( A_{rG,cG}\right) x^{n-\left|G\right|} . \end{equation}

Proposition 1' is part of Corollary 6.164 in my Notes on the combinatorial fundamentals of algebra, in the version of 10 January 2019. (In those notes, I'm using slightly different notations: Namely, what I am calling $A_{rG,cG}$ here is called $\operatorname{sub}^{w\left(G\right)}_{w\left(G\right)} A$ in my notes.) Proposition 1 follows from Proposition 1' (applied to $x=1$).

Let me sketch a proof of Proposition 1 by handwaving, lest my reference creates the impression that it is complicated (it is, if one wants to have a formal proof, but intuitively it's rather obvious):

Hint to the proof of Proposition 1. Write $A$ in the form $\left( a_{i,j}\right) _{1\leq i\leq n,\ 1\leq j\leq n}$. Compute $\det\left( I_{n}+A\right) $ using Laplace expansion; the result is a sum of $n!$ products. Expand each of these products further by getting rid of the parentheses around the diagonal entries $1+a_{i,i}$. Then, combine terms which share the same set of indices occuring under the $a$'s; the resulting sub-sums are the $\det\left( A_{rG,cG}\right) $ for $G\subseteq\left[ n\right] $. For instance, for $n=3$, this argument goes as follows: \begin{align} & \det\left( I_{n}+A\right) \\ & = \det\left( \begin{array}[c]{ccc} 1+a_{1,1} & a_{1,2} & a_{1,3}\\ a_{2,1} & 1+a_{2,2} & a_{2,3}\\ a_{3,1} & a_{3,2} & 1+a_{3,3} \end{array} \right) \\ & = \left( 1+a_{1,1}\right) \left( 1+a_{2,2}\right) \left( 1+a_{3,3} \right) +a_{1,2}a_{2,3}a_{3,1}+a_{1,3}a_{2,1}a_{3,2} \\ & \qquad -\left( 1+a_{1,1}\right) a_{2,3}a_{3,2}-a_{1,2}a_{2,1}\left( 1+a_{3,3}\right) -a_{1,3}\left( 1+a_{2,2}\right) a_{3,1} \\ & = a_{1,1}a_{2,2}-a_{1,2}a_{2,1}+a_{1,1}a_{3,3}-a_{1,3}a_{3,1}+a_{2,2}a_{3,3} \\ & \qquad -a_{2,3}a_{3,2}+a_{1,1}a_{2,2}a_{3,3}-a_{1,1}a_{2,3}a_{3,2}-a_{1,2} a_{2,1}a_{3,3} \\ & \qquad +a_{1,2}a_{3,1}a_{2,3}+a_{2,1}a_{1,3}a_{3,2}-a_{1,3}a_{2,2}a_{3,1} +a_{1,1}+a_{2,2}+a_{3,3}+1 \\ & = \underbrace{a_{1,1}a_{2,2}a_{3,3}+a_{1,2}a_{2,3}a_{3,1}+a_{1,3} a_{2,1}a_{3,2}-a_{1,1}a_{2,3}a_{3,2}-a_{1,2}a_{2,1}a_{3,3}-a_{1,3} a_{2,2}a_{3,1}}_{=\det A=\det\left( A_{r\left\{ 1,2,3\right\} ,c\left\{ 1,2,3\right\} }\right) } \\ & \qquad +\underbrace{a_{1,1}a_{2,2}-a_{1,2}a_{2,1}}_{=\det\left( A_{r\left\{ 1,2\right\} ,c\left\{ 1,2\right\} }\right) }+\underbrace{a_{1,1} a_{3,3}-a_{1,3}a_{3,1}}_{=\det\left( A_{r\left\{ 1,3\right\} ,c\left\{ 1,3\right\} }\right) } \\ & \qquad +\underbrace{a_{2,2}a_{3,3}-a_{2,3}a_{3,2}}_{=\det\left( A_{r\left\{ 2,3\right\} ,c\left\{ 2,3\right\} }\right) }+\underbrace{a_{1,1}} _{=\det\left( A_{r\left\{ 1\right\} ,c\left\{ 1\right\} }\right) } \\ & \qquad +\underbrace{a_{2,2}}_{=\det\left( A_{r\left\{ 2\right\} ,c\left\{ 2\right\} }\right) }+\underbrace{a_{3,3}}_{=\det\left( A_{r\left\{ 3\right\} ,c\left\{ 3\right\} }\right) }+\underbrace{1}_{=\det\left( A_{r\varnothing,c\varnothing}\right) } \\ & = \sum\limits_{G\subseteq\left[ n\right] }\det\left( A_{rG,cG}\right) . \end{align}

As a corollary of Proposition 1, we obtain:

Corollary 2. Let $n\in\mathbb{N}$ and $A\in\mathbf{k}^{n\times n}$. Let $a_{1},a_{2},\ldots,a_{n}\in\mathbf{k}$. For each subset $G$ of $\left[ n\right] $, set $a_{G}=\prod_{g\in G}a_{g}\in\mathbf{k}$. Then, \begin{equation} \det\left( I_{n}+\operatorname*{diag}\left( a_{1},a_{2},\ldots ,a_{n}\right) A\right) =\sum\limits_{G\subseteq\left[ n\right] }a_{G} \det\left( A_{rG,cG}\right) . \end{equation}

Proof of Corollary 2. Let $G$ be a subset of $\left[n\right]$. Write this subset $G$ in the form $\left\{g_1 < g_2 < \cdots < g_k\right\}$. Then, $\prod_{i=1}^k a_{g_i} = \prod_{g\in G} a_g = a_G$.

For each $i \in \left[k\right]$, the $i$-th row of the matrix $A_{rG, cG}$ is a subsequence of the $g_i$-th row of the matrix $A$ (because of how $A_{rG, cG}$ is defined).

But $\operatorname*{diag}\left( a_{1},a_{2},\ldots,a_{n}\right) A$ is the matrix obtained from $A$ by multiplying its $i$-th row with $a_i$ for each $i \in \left[n\right]$. Hence, $\left(\operatorname*{diag}\left( a_{1},a_{2},\ldots,a_{n}\right) A\right)_{rG, cG}$ is the matrix obtained from $A_{rG, cG}$ by multiplying its $i$-th row with $a_{g_i}$ for each $i \in \left[k\right]$ (because $G = \left\{g_1 < g_2 < \cdots < g_k\right\}$). Hence, the determinant of this matrix $\left(\operatorname*{diag}\left( a_{1},a_{2},\ldots,a_{n}\right) A\right)_{rG, cG}$ is \begin{equation} \left(\prod\limits_{i=1}^k a_{g_i}\right) \det\left(A_{rG, cG}\right) . \end{equation} In other words, \begin{align} \det\left(\left(\operatorname*{diag}\left( a_{1},a_{2},\ldots,a_{n}\right) A\right)_{rG, cG}\right) & = \underbrace{\left(\prod\limits_{i=1}^k a_{g_i}\right)}_{= a_G} \det\left(A_{rG, cG}\right) \\ & = a_G \det\left(A_{rG, cG}\right) . \label{darij.eq.0} \tag{1} \end{align}

Now, forget that we fixed $G$. We thus have proven that \eqref{darij.eq.0} holds for each subset $G$ of $\left[n\right]$.

Now, Proposition 1 (applied to $\operatorname*{diag}\left( a_{1},a_{2},\ldots,a_{n}\right) A$ instead of $A$) yields \begin{align} & \det\left( I_{n}+\operatorname*{diag}\left( a_{1},a_{2},\ldots ,a_{n}\right) A\right) \\ & = \sum\limits_{G\subseteq\left[ n\right] } \det\left(\left(\operatorname*{diag}\left( a_{1},a_{2},\ldots,a_{n}\right) A\right)_{rG, cG}\right) \\ & = \sum\limits_{G\subseteq\left[ n\right] }a_{G} \det\left( A_{rG,cG}\right) \end{align} (by \eqref{darij.eq.0}). This proves Corollary 2. $\blacksquare$

Proposition 3. Let $n\in\mathbb{N}$ and $m\in\mathbb{N}$. Let $A\in\mathbf{k}^{n\times m}$ and $B\in\mathbf{k}^{m\times n}$. Then, \begin{equation} \det\left( I_{n}+AB\right) =\det\left( I_{m}+BA\right) . \end{equation}

Proposition 3 is known as Sylvester's determinant theorem (the link goes to a Wikipedia article which contains a proof); it also appears on math.stackexchange (again with proofs, this time more readable). $\blacksquare$

Finally, let me state the Cauchy-Binet formula in appropriate language:

Theorem 4. Let $n\in\mathbb{N}$ and $m\in\mathbb{N}$. Let $A\in \mathbf{k}^{m\times n}$ and $B\in\mathbf{k}^{n\times m}$. Then, \begin{equation} \det\left( AB\right) =\sum\limits_{\substack{J\subseteq\left[ n\right] ;\\\left\vert J\right\vert =m}}\det\left( A_{cJ}\right) \det\left( B_{rJ}\right) . \end{equation}

Now, let me state my favorite version of your claim:

Theorem 5. Let $n\in\mathbb{N}$ and $m\in\mathbb{N}$. Let $B\in \mathbf{k}^{m\times n}$ and $C\in\mathbf{k}^{n\times m}$ be such that $CB=I_{n}$. Let $M=BC$. Then, every subset $G$ of $\left[ m\right] $ satisfies \begin{equation} \det\left( M_{rG,cG}\right) =\sum\limits_{\substack{J\subseteq\left[ m\right] ;\\\left\vert J\right\vert =n;\\G\subseteq J}}\det\left( B_{rJ}\right) \det\left( C_{cJ}\right) . \end{equation}

How to get from Theorem 5 to your conjecture? Notice that my $G$ and $J$ are your $k$ and $j$. Set $C=\left( AB\right) ^{-1}A$ and observe that $CB=I_{n}$ and $M=BC$; furthermore, use $C=\left( AB\right) ^{-1}A$ to observe that $C_{cJ}=\left( \left( AB\right) ^{-1}A\right) _{cJ}=\left( AB\right) ^{-1}A_{cJ}$ and thus $\det\left( C_{cJ}\right) =\underbrace{\det \left( \left( AB\right) ^{-1}\right) }_{=\dfrac{1}{\Delta}}\det\left( A_{cJ}\right) =\dfrac{1}{\Delta}\det\left( A_{cJ}\right) $, so that my $\det\left( B_{rJ}\right) \det\left( C_{cJ}\right) $ is your $\dfrac {1}{\Delta}d_{J}$. Now, Theorem 5 quickly turns into your claim. (I don't know how real the extra generality of Theorem 5 is, though; it does seem harder to derive it back from your conjecture, at least.)

Proof of Theorem 5. Let $\mathbf{m}$ be the polynomial ring $\mathbf{k} \left[ x_{1},x_{2},\ldots,x_{m}\right] $ over $\mathbf{k}$ in $m$ commuting indeterminates $x_{1},x_{2},\ldots,x_{m}$. Then, $\mathbf{k}$ is a subring of $\mathbf{m}$, so that $\mathbf{k}^{n\times m}\subseteq\mathbf{m}^{n\times m}$ and $\mathbf{k}^{m\times n}\subseteq\mathbf{m}^{m\times n}$. Define a matrix $\widetilde{B}\in\mathbf{m}^{m\times n}$ by $\widetilde{B} =\operatorname*{diag}\left( 1+x_{1},1+x_{2},\ldots,1+x_{m}\right) \cdot B$. For each subset $G$ of $\left[ m\right] $, set $x_{G}=\prod_{g\in G}x_{g} \in\mathbf{m}$.

Every subset $J$ of $\left[ m\right] $ satisfies \begin{align} \det\left( \widetilde{B}_{rJ}\right) =\left( \sum \limits_{G\subseteq J}x_{G}\right) \det\left( B_{rJ}\right) . \label{darij.eq.1} \tag{2} \end{align}

Proof of \eqref{darij.eq.1}: Let $J$ be a subset of $\left[ m\right] $. Write $J$ in the form $\left\{ j_{1}<j_{2}<\cdots<j_{k}\right\} $. Now, $\widetilde{B} =\operatorname*{diag}\left( 1+x_{1},1+x_{2},\ldots,1+x_{m}\right) \cdot B$; in other words, $\widetilde{B}$ is the result of multiplying the $i$-th row of $B$ with $1+x_{i}$ for each $i\in\left[ m\right] $. Hence, $\widetilde{B} _{rJ}$ is the result of multiplying the $i$-th row of $\widetilde{B}$ with $1+x_{j_{i}}$ for each $i\in\left[ k\right] $. Therefore, \begin{align} \det\left( \widetilde{B}_{rJ}\right) =\left( \prod_{i\in\left[ k\right] }\left( 1+x_{j_{i}}\right) \right) \det\left( B_{rJ}\right) . \end{align} But since $\prod_{i\in\left[ k\right] }\left( 1+x_{j_{i}}\right) =\sum\limits_{G\subseteq J}x_{G}$ (this is a classical identity), this rewrites as \begin{align} \det\left( \widetilde{B}_{rJ}\right) =\left( \sum\limits_{G\subseteq J} x_{G}\right) \det\left( B_{rJ}\right) . \end{align} Thus, \eqref{darij.eq.1} is proven.

Note that \begin{align} \widetilde{B} &= \underbrace{\operatorname*{diag}\left( 1+x_{1},1+x_{2} ,\ldots,1+x_{m}\right) }_{=I_{m}+\operatorname*{diag}\left( x_{1} ,x_{2},\ldots,x_{m}\right) }\cdot B \\ & = \left( I_{m}+\operatorname*{diag}\left( x_{1},x_{2},\ldots ,x_{m}\right) \right) B . \label{darij.eq.2} \tag{3} \end{align}

On the other hand, Corollary 2 (applied to $\mathbf{m}$, $m$, $M$, $x_{i}$ and $x_{G}$ instead of $\mathbf{k}$, $n$, $A$, $a_{i}$ and $a_{G}$) shows that \begin{align} \det\left( I_{m}+\operatorname*{diag}\left( x_{1},x_{2} ,\ldots,x_{m}\right) M\right) =\sum\limits_{G\subseteq\left[ m\right] }x_{G} \det\left( M_{rG,cG}\right) . \label{darij.eq.3} \tag{4} \end{align}

But Proposition 3 (applied to $\mathbf{m}$, $C$ and $\operatorname*{diag} \left( x_{1},x_{2},\ldots,x_{m}\right) B$ instead of $\mathbf{k}$, $A$ and $B$) yields \begin{align} & \det\left( I_{n}+C\operatorname*{diag}\left( x_{1},x_{2},\ldots ,x_{m}\right) B\right) \\ & = \det\left( I_{m}+\operatorname*{diag}\left( x_{1},x_{2},\ldots ,x_{m}\right) \underbrace{BC}_{=M}\right) \\ & =\det\left( I_{m}+\operatorname*{diag}\left( x_{1},x_{2},\ldots ,x_{m}\right) M\right) \\ & = \sum\limits_{G\subseteq\left[ m\right] }x_{G}\det\left( M_{rG,cG}\right) \end{align} (by \eqref{darij.eq.3}). Hence, \begin{align} & \sum\limits_{G\subseteq\left[ m\right] }x_{G}\det\left( M_{rG,cG}\right) \\ & = \det\left( \underbrace{I_{n}}_{=CB}+C\operatorname*{diag}\left( x_{1},x_{2},\ldots,x_{m}\right) B\right) \\ & = \det\left( \underbrace{CB+C\operatorname*{diag}\left( x_{1},x_{2} ,\ldots,x_{m}\right) B}_{=C\left( I_{m}+\operatorname*{diag}\left( x_{1},x_{2},\ldots,x_{m}\right) \right) B}\right) \\ & =\det\left( C\underbrace{\left( I_{m}+\operatorname*{diag}\left( x_{1},x_{2},\ldots,x_{m}\right) \right) B}_{\substack{=\widetilde{B} \\\text{(by \eqref{darij.eq.2})}}}\right) \\ & =\det\left( C\widetilde{B}\right) =\sum\limits_{\substack{J\subseteq\left[ m\right] ;\\\left\vert J\right\vert =n}}\det\left( C_{cJ}\right) \underbrace{\det\left( \widetilde{B}_{rJ}\right) }_{\substack{=\left( \sum\limits_{G\subseteq J}x_{G}\right) \det\left( B_{rJ}\right) \\\text{(by \eqref{darij.eq.1})}}} \\ & \qquad \qquad \left( \begin{array}{c} \text{by Theorem 4, applied to $\mathbf{m}$, $m$, $n$, $C$ and $\widetilde{B}$} \\ \text{instead of $\mathbf{k}$, $n$, $m$, $A$ and $B$} \end{array} \right) \\ & =\sum\limits_{\substack{J\subseteq\left[ m\right] ;\\\left\vert J\right\vert =n}}\det\left( C_{cJ}\right) \left( \sum\limits_{G\subseteq J}x_{G}\right) \det\left( B_{rJ}\right) \\ & = \sum\limits_{\substack{J\subseteq\left[ m\right] ;\\\left\vert J\right\vert =n}}\left( \sum\limits_{G\subseteq J}x_{G}\right) \det\left( B_{rJ}\right) \det\left( C_{cJ}\right) \\ & = \sum\limits_{G\subseteq\left[ m\right] }\left( \sum \limits_{\substack{J\subseteq\left[ m\right] ;\\\left\vert J\right\vert =n;\\G\subseteq J}}\det\left( B_{rJ}\right) \det\left( C_{cJ}\right) \right) x_{G} . \end{align} This is an equality between two polynomials in $\mathbf{m}=\mathbf{k}\left[ x_{1},x_{2},\ldots,x_{m}\right] $. Comparing the coefficients of the monomials before $x_{G}$ on both sides of this equality, we conclude that \begin{align} \det\left( M_{rG,cG}\right) =\sum\limits_{\substack{J\subseteq\left[ m\right] ;\\\left\vert J\right\vert =n;\\G\subseteq J}}\det\left( B_{rJ}\right) \det\left( C_{cJ}\right) \qquad \text{for every subset $G$ of $\left[ m\right] $} . \end{align} This proves Theorem 5. $\blacksquare$

$\endgroup$
  • $\begingroup$ This is amazing! I can't thank you enough! I'm still digesting the proof, but if you don't mind I have a quick clarifying question: in Theorem 4 shouldn't the summation be over $J \subseteq [n]$ with the additional constraint that $J$ have $m$ elements? $\endgroup$ – mzp Apr 21 '16 at 11:02
  • $\begingroup$ Fixed -- thank you! (and thanks for the interesting question, too.) $\endgroup$ – darij grinberg Apr 21 '16 at 13:30

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.