4
$\begingroup$

I'm interested in understanding whether a particular natural function on matrices, closely related to the permanent of a matrix, is invertible, and whether its inverse admits a simple closed form. The function $f$ I'm concerned with maps doubly stochastic $n \times n$ matrices to doubly stochastic $n \times n$ matrices, and is given by the following expression.

$ f_{ij}(A) = \frac{A_{ij} \ perm(\tilde{A}_{ij})}{perm(A)} $

where $perm$ denotes the permanent function, and $\tilde{A}_{ij}$ denotes the $(i,j)$'th minor of $A$ --- i.e. the matrix gotten by removing the i'th row and j'th column of $A$. Observe that, by the row [column] expansion formula for the permanent, $f(A)$ is doubly stochastic whenever A is doubly stochastic. Also observe that $f$ is continuous, and each entry of $f(A)$ is the ratio of two multilinear functions of the entries of $A$.

I have three questions:

(a) Is $f$ invertible? If not, does $f$ at least have a right inverse, and is there such a right inverse that is continuous?

(b) If $f$ has an inverse, is there a simple closed form for $f^{-1}$? Otherwise, if $f$ has a continuous right-inverse, is there a simple closed form for this right inverse?

(c) If $f$ has an inverse (or continuous right-inverse), but the answer to (b) is no, can the inverse at least be (approximately) computed by a simple, preferably efficient (polynomial-time in n) procedure?

  • 0
    Gerry: The 2x2 case is simple. $f^-{1}(A)$ simply takes the square root of each entry of $A$, and rescales to restore stochasticity. The 3x3 case involves 9 variables, and appears nontrivial to invert, though doing so mechanically would be the next thing to try in order to see if the form of the inverse reveals some structure.2012-05-07

0 Answers 0