Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
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. –  Gerry Myerson May 3 '12 at 6:53
    
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. –  joriki May 3 '12 at 9:15
    
Joriki: You are right. I meant to say that the "interesting" part of $f$, the numerator, is a multilinear function. Will correct. –  srd May 3 '12 at 12:24
    
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... –  srd May 3 '12 at 12:45
    
Thanks. So...have you calculated any examples? –  Gerry Myerson May 4 '12 at 13:11

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.