How to combine linear constraints on a matrix and its inverse? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-25T18:08:35Z http://mathoverflow.net/feeds/question/31251 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/31251/how-to-combine-linear-constraints-on-a-matrix-and-its-inverse How to combine linear constraints on a matrix and its inverse? Frederick Eberhardt 2010-07-09T21:44:30Z 2010-08-23T11:07:19Z <p>Suppose there exists a $(n \times n)$ matrix $A$ that is real and invertible (nothing unusual or special about $A$). We do not know the entries of $A$. However, we do have linear constraints, some of which are on the entries of $A$ and some of which are on the entries of its inverse $A^{-1}$. All constraints are assumed to be consistent with the true invertible matrix $A$, but the system may be underdetermined.</p> <p>The general question is whether there is an efficient way to solve the system and determine $A$ or to characterize the remaining underdetermination in $A$. How can the linear constraints on $A^{-1}$ be converted into constraints on $A$ such that one can still solve for $A$ (when the system is determined)?</p> <p>Simplest case: I know some entries of $A$ and some entries of $A^{-1}$. How can these constraints be combined to solve for $A$, if possible? Obviously, $AA^{-1} = I$, but in general this is a quadratic system in many variables, for which I am unaware of any solution procedure.</p> <p>Even general pointers would be most welcome. </p> http://mathoverflow.net/questions/31251/how-to-combine-linear-constraints-on-a-matrix-and-its-inverse/31257#31257 Answer by Mau for How to combine linear constraints on a matrix and its inverse? Mau 2010-07-09T22:49:32Z 2010-07-09T22:49:32Z <p>I don't have 'the power' to leave comments, so I'll shoot some stuff here.</p> <p>You could use the simplex algorithm to find <em>a</em> solution for $A$ feasible WRT only the constraints on $A$. It would be cool if you could exploit the primal-dual version of the algorithm to consider the constraints on $A^{-1}$ in the dual phase, but I have no idea whether the dual of the problem defined with the constraints on $A$ has any relation with the problem defined with the constraints on $A^{-1}$.</p> http://mathoverflow.net/questions/31251/how-to-combine-linear-constraints-on-a-matrix-and-its-inverse/34867#34867 Answer by Aaron Meyerowitz for How to combine linear constraints on a matrix and its inverse? Aaron Meyerowitz 2010-08-07T21:26:26Z 2010-08-07T21:26:26Z <p>This is more in the nature general observations, but: If you have 3 nxn symbolic matrices then AB=C is $n^2$ simultaneous equations in $3n^2$ variables. One could generalize in many directions but I will stick to your case of C being the identity matrix. So we start from a generic pair of real matrices with AB=I, then erase some entries of each (between them, N in all), replace them with variables (optionally with linear bounds) then attempt to reconstruct the matrices (either would give the other). So we have $n^2$ simultaneous quadratic equations in N unknowns, perhaps with bounds thrown in. if $n^2 \lt N$ there would seem no hope. If A=B=I and we erase the top left entries of each, we only know that they are on a hyperbola $A_{1,1}B_{1,1}=1$. If we had additional constraints that both were in [-2,2] then we could refine to both being in [-2,-1/2] or both in [1/2,2] but no further. If we start with A random but well behaved (all entries and eigenvalues bounded away from 0, perhaps), compute the inverse B (also well behaved), then choose N entries at random to hide, spread between A and B, $N\lt\lt n^2$ then we would likely end up with some equations 0=0 or 1=1 but we would also might end up with enough linear equations to solve for some of the variables. This might make other equations linear and so on. </p> <p>Starting with initial values (in the bounds) there are Multi-Dimensional Newton's Method which could be applied. </p> <p>In the event that we have A and B diagonal but the entries are bounded to be in [-1.1,1.1] then we end up with $2^n$ cases. If they are all bounded to be in [1/2,2] then there are n cases. Thus I'd expect sensitivity to initial conditions.</p> http://mathoverflow.net/questions/31251/how-to-combine-linear-constraints-on-a-matrix-and-its-inverse/36373#36373 Answer by Tsuyoshi Ito for How to combine linear constraints on a matrix and its inverse? Tsuyoshi Ito 2010-08-22T12:39:02Z 2010-08-23T11:07:19Z <p>Since the question suggests that the questioner is looking for an <em>efficient</em> algorithm for this problem, here is my attempt to answer the question from the complexity-theoretic perspective. Unfortunately, the answer is pretty negative.</p> <p>The following problem, which is one of the possible formulations of the question, is NP-complete.</p> <p><em>Given</em>: N∈ℕ, finitely many linear constraints (equations or inequalities) over ℚ on variables a<sub>ij</sub> and b<sub>ij</sub> (1≤i,j≤N), and N×N rational matrices A and B satisfying AB=I and all the given linear constraints.<br> <em>Question</em>: Is there another pair (A, B) of N×N rational matrices that satisfy AB=I and all the given linear constraints?</p> <p>A proof is by reduction from the following problem (called “Another Solution Problem (ASP) of SAT”):</p> <p><em>Given</em>: An instance φ of <a href="http://en.wikipedia.org/wiki/Boolean_satisfiability_problem" rel="nofollow">SAT</a> and a satisfying assignment to φ.<br> <em>Question</em>: Is there another satisfying assignment to φ?</p> <p>The ASP of SAT is known to be NP-complete [YS03].</p> <p><em>Note: The following reduction is much simplified compared to the first version posted. See below for the first version, which proves a slightly stronger result.</em></p> <p>We can construct a reduction from the ASP of SAT to the problem in question as follows. Given an instance of SAT with n variables x<sub>1</sub>,…,x<sub>n</sub>, let N=n and constrain A to be a diagonal matrix such that A=A<sup>−1</sup>; these are easily written as linear equality constraints on the elements of A and A<sup>−1</sup>. These constraints are equivalent to the condition that A is a diagonal matrix whose diagonal elements are ±1. Now encode a truth assignment to the n variables by such a matrix by letting a<sub>ii</sub>=1 if x<sub>i</sub> is true and a<sub>ii</sub>=−1 otherwise. Now it is easy to write down the constraints in SAT as linear inequalities.</p> <p>With this encoding, the solutions to the given instance of SAT correspond one-to-one to the pairs (A, A<sup>−1</sup>) satisfying all the linear constraints. This establishes a reduction from the ASP of SAT to the problem in question, and therefore the problem in question is NP-complete.</p> <p><em>Remark</em>. This reduction can be viewed as an ASP reduction from SAT to the problem of finding a pair (A, B) of matrices satisfying given linear constraints. For more about ASP reductions, see [UN96] and/or [YS03]. (The notion of ASP reductions was used in [UN96], where the authors treated it as a parsimonious reduction with a certain additional property. The term “ASP reduction” was introduced in [YS03].)</p> <hr> <p>In fact, the problem remains NP-complete even if we allow only linear constraints on the variables a<sub>ij</sub> and linear constraints on the variables b<sub>ij</sub> (but not a linear constraint which uses both a<sub>ij</sub> and b<sub>kl</sub>). The NP-completeness of this restricted problem can also be shown by reduction from the ASP of SAT.</p> <p>The following lemma is a key to construct this version of a reduction.</p> <p><strong>Lemma</strong>. Let A be a real symmetric invertible matrix. Both A and A<sup>−1</sup> are stochastic if and only if A is the permutation matrix of a permutation whose order is at most 2.</p> <p>I guess that this lemma can be proved more elegantly, but anyway the following proof should be at least correct.</p> <p><strong>Proof</strong>. The “if” part is straightforward. To prove the “only if” part, assume that both A and A<sup>−1</sup> are stochastic. Note the following properties of A:</p> <ul> <li>Because A is symmetric, A can be diagonalizable and all eigenvalues are real.</li> <li>Because A is stochastic, all eigenvalues have modulus at most 1.</li> <li>Because A<sup>−1</sup> is stochastic, all eigenvalues have modulus at least 1.</li> </ul> <p>Therefore, A can be diagonalizable and all eigenvalues are ±1, and therefore A is an orthogonal matrix. Since both the 1-norm and the 2-norm of each row are equal to 1, all but one entry in each row are 0. Therefore, A is a permutation matrix, and the only symmetric permutation matrices are the permutation matrices of some permutations whose order is at most 2. (end of proof of Lemma 1)</p> <p>It is easy to write down linear constraints which enforce A to be symmetric and both A and A<sup>−1</sup> to be stochastic. In addition, write down linear constraints which enforce A to be block diagonal with 2×2 blocks. Given an instance of SAT with n variables x<sub>1</sub>,…,x<sub>n</sub>, we encode a truth assignment by a 2n×2n matrix which is block diagonal with 2×2 blocks so that the first block is <code>$\pmatrix{1 &amp; 0 \\ 0 &amp; 1}$</code> if x<sub>1</sub> is true and the first block is <code>$\pmatrix{0 &amp; 1 \\ 1 &amp; 0}$</code> if x<sub>1</sub> is false and so on.</p> <p>Now that a truth assignment can be encoded as a matrix, the rest is the same: just verify that it is easy to write down the constraints in SAT as linear inequalities and that there is one-to-one correspondence between the solutions to a SAT instance and the pairs (A, A<sup>−1</sup>) of matrices satisfying the linear constraints.</p> <hr> <p>References</p> <p>[UN96] Nobuhisa Ueda and Tadaaki Nagao. NP-completeness results for NONOGRAM via parsimonious reductions. <em>Technical Report TR96-0008</em>, Department of Computer Science, Tokyo Institute of Technology, May 1996.</p> <p>[YS03] Takayuki Yato and Takahiro Seta. Complexity and completeness of finding another solution and its application to puzzles. <em>IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences</em>, E86-A(5):1052–1060, May 2003.</p>