Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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....?

share|improve this question
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.