How to combine linear constraints on a matrix and its inverse? - MathOverflow

How to combine linear constraints on a matrix and its inverse?

2010-07-09T21:44:30Z

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.

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

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.

Even general pointers would be most welcome.

Answer by Mau for How to combine linear constraints on a matrix and its inverse?

2010-07-09T22:49:32Z

I don't have 'the power' to leave comments, so I'll shoot some stuff here.

You could use the simplex algorithm to find a 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}$.

Answer by Aaron Meyerowitz for How to combine linear constraints on a matrix and its inverse?

2010-08-07T21:26:26Z

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.

Starting with initial values (in the bounds) there are Multi-Dimensional Newton's Method which could be applied.

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.

Answer by Tsuyoshi Ito for How to combine linear constraints on a matrix and its inverse?

2010-08-22T12:39:02Z

Since the question suggests that the questioner is looking for an efficient algorithm for this problem, here is my attempt to answer the question from the complexity-theoretic perspective. Unfortunately, the answer is pretty negative.

The following problem, which is one of the possible formulations of the question, is NP-complete.

Given: N∈ℕ, finitely many linear constraints (equations or inequalities) over ℚ on variables a_ij and b_ij (1≤i,j≤N), and N×N rational matrices A and B satisfying AB=I and all the given linear constraints.
Question: Is there another pair (A, B) of N×N rational matrices that satisfy AB=I and all the given linear constraints?

A proof is by reduction from the following problem (called “Another Solution Problem (ASP) of SAT”):

Given: An instance φ of SAT and a satisfying assignment to φ.
Question: Is there another satisfying assignment to φ?

The ASP of SAT is known to be NP-complete [YS03].

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.

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₁,…,x_n, let N=n and constrain A to be a diagonal matrix such that A=A⁻¹; these are easily written as linear equality constraints on the elements of A and A⁻¹. 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_ii=1 if x_i is true and a_ii=−1 otherwise. Now it is easy to write down the constraints in SAT as linear inequalities.

With this encoding, the solutions to the given instance of SAT correspond one-to-one to the pairs (A, A⁻¹) 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.

Remark. 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].)

In fact, the problem remains NP-complete even if we allow only linear constraints on the variables a_ij and linear constraints on the variables b_ij (but not a linear constraint which uses both a_ij and b_kl). The NP-completeness of this restricted problem can also be shown by reduction from the ASP of SAT.

The following lemma is a key to construct this version of a reduction.

Lemma. Let A be a real symmetric invertible matrix. Both A and A⁻¹ are stochastic if and only if A is the permutation matrix of a permutation whose order is at most 2.

I guess that this lemma can be proved more elegantly, but anyway the following proof should be at least correct.

Proof. The “if” part is straightforward. To prove the “only if” part, assume that both A and A⁻¹ are stochastic. Note the following properties of A:

Because A is symmetric, A can be diagonalizable and all eigenvalues are real.
Because A is stochastic, all eigenvalues have modulus at most 1.
Because A⁻¹ is stochastic, all eigenvalues have modulus at least 1.

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)

It is easy to write down linear constraints which enforce A to be symmetric and both A and A⁻¹ 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₁,…,x_n, we encode a truth assignment by a 2n×2n matrix which is block diagonal with 2×2 blocks so that the first block is $\pmatrix{1 & 0 \\ 0 & 1}$ if x₁ is true and the first block is $\pmatrix{0 & 1 \\ 1 & 0}$ if x₁ is false and so on.

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⁻¹) of matrices satisfying the linear constraints.

References

[UN96] Nobuhisa Ueda and Tadaaki Nagao. NP-completeness results for NONOGRAM via parsimonious reductions. Technical Report TR96-0008, Department of Computer Science, Tokyo Institute of Technology, May 1996.

[YS03] Takayuki Yato and Takahiro Seta. Complexity and completeness of finding another solution and its application to puzzles. IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, E86-A(5):1052–1060, May 2003.