4 slight changes for better wording, fixed typo

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

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 x1,…,xn, let N=n and constrain A to be a diagonal matrix such that A=A−1; these are easily written as linear equality constraints on the elements of A and A−1. 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 the i-th diagonal element be aii=1 if xi is true and 1 aii=−1 otherwise. Now it is easy to write down the constraints in SAT as linear inequalities.

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 [YS06]. YS03]. (The term notion of ASP reduction reductions was introduced used in [YS03]. [UN96] did not give a term for this notion and UN96], where the authors treated it as a parsimonious reduction with a certain additional property.)property. The term ASP reduction was introduced in [YS03].)

3 simplified a proof, expanded discussions

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

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 x1,…,xn, let N=n and constrain A to be a diagonal matrix such that A=A1; these are easily written as linear equality constraints on the elements of A and A1. 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 the i-th diagonal element be 1 if xi is true and 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, A1) 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 [YS06]. (The term ASP reduction was introduced in [YS03]. [UN96] did not give a term for this notion and treated it as a parsimonious reduction with a certain additional property.)

In fact, the problem remains NP-complete even if we allow only linear constraints on the variables aij and linear constraints on the variables bij (but not a linear constraint which uses both aij and bkl). 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.

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 .

With this encoding, and that there is one-to-one correspondence between the solutions to the given instance of a SAT correspond one-to-one to instance and the pairs (A, A−1) of matrices satisfying all the linear constraints.This establishes a reduction from the ASP

References

[UN96] Nobuhisa Ueda and Tadaaki Nagao. NP-completeness results for NONOGRAM via parsimonious reductions. Technical Report TR96-0008, Department of SAT to the problem in questionComputer Science, and therefore the problem in question is NP-completeTokyo Institute of Technology, May 1996.

References

2 added 91 characters in body

Since the question suggests that the questioner is looking for an efficient algorithm for this problem, I give a negative answer from the complexity-theoretic perspective.

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 aij and bij (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].

The following lemma is a key to construct a reduction.

Lemma. Let A be a real symmetric invertible matrix. Both A and A−1 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−1 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−1 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−1 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 x1,…,xn, 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 x1 is true and the first block is $\pmatrix{0 & 1 \\ 1 & 0}$ if x1 is false and so on. 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−1) 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.

References

[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.

1