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

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.