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.
Best Answer
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 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].
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=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 aii=1 if xi is true and aii=−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−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.
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 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.
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:
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 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−1) 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.