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?

  • 1
    I'm interested to know where you came across this function $f$. I'm also interested to know whether you have calculated any examples, which might give you some idea of whether it is invertible, what an inverse might look like, etc.2012-05-03
  • 0
    I don't think each entry of $f(A)$ is a multilinear function of the entries of $A$ -- the entries of $A$ also appear in the permanent in the denominator.2012-05-03
  • 0
    Joriki: You are right. I meant to say that the "interesting" part of $f$, the numerator, is a multilinear function. Will correct.2012-05-03
  • 0
    Gerry: Where this function comes from, and why we want to invert it, is a long story, but here is a brief explanation. Consider the procedure that takes in a matrix $A$, and samples non-uniformly a random matching of the complete $n \times n$ bipartite graph, such that the probability of matching $M$ is proportional to the product of the weight of its edges as given by $A$. If you do the calculation, you observe that the random choice of $M$ contains $(i,j)$ with probability $f_{ij}(A)$. Now, why I'm interested in inverting $f$ would take much longer to explain...2012-05-03
  • 0
    Thanks. So...have you calculated any examples?2012-05-04
  • 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