# A Conjecture related to minimization of product of determinants over permutations

Hi

I have the following problem (and a conjecture which holds in Matlab). Given an $N\times N$ matrix $H$, represent it by its $2N\times 2N$ real-valued representation (which I will also denote by $H$ as the complex $H$ will not be used any further) $$H = \left[\begin{array}{cc} \mathcal{R}(H)& -\mathcal{I}(H) \newline \mathcal{I}(H)& \mathcal{R}(H)\end{array}\right].$$ $N$ is always an even number.

I will now denote the first $N$ columns of $H$ by $x_1,\ldots,x_N$ and the last $N$ columns by $y_1,\ldots,y_N$. Now define the matrix $$C=I-H^{\mathrm{T}}(HH^{\mathrm{T}} + \alpha I)^{-1}H,$$ for some $\alpha>0$. By assumption, all values in $C$ are non-zero.

I am now interested in grouping the columns of $H$ 2-by-2 (Later I will generalize to M-by-M if the conjecture is correct) in some order so that I get $N$ pairs of columns. For example, with $N=4$ one such pairing would be $$(x_1,x_3),(x_2,y_1),(y_4,x_4),(y_2,y_3)$$ so I am allowed to group "one x with one y" but also "one x with another x" etc. To each such pairing there is a corresponding permutation of the columns $\sigma$. I will write this $\sigma$ as $$\sigma = \{v_{11}\,v_{12},v_{21}\,v_{22},\ldots,v_{N1}\,v_{N2}\}$$ to better visualize the pairs within the permutation.

Define the $2\times 2$ sub matrix of $C$ $$C_k = \left[\begin{array}{cc} C_{v_{k1}v_{k1}} & C_{v_{k1}v_{k2}} \newline C_{v_{k2}v_{k1}} & C_{v_{k2}v_{k2}}\end{array}\right].$$ Now, the cost function is $$f(\sigma) = \prod_{k=1}^N \det(C_k)$$ and I would like to minimize this over $\sigma$.

Conjecture: (i) The optimal $\sigma$ is such that if I pair $x_i$ with $x_j$, then I will also pair $y_i$ with $y_j$. (ii) If I pair $x_i$ with $y_j$, then I will also pair $y_i$ with $x_j$. (iii) I will never pair $x_i$ with $y_i$.

The assumption of all elements in $C$ being non-zero is important for (iii).

Is this true....?

-