Determine unknown matrix function of particular form from known points

Question

I encountered the following problem recently in a practical context.

Fix $n \ge 1$. Suppose $f$ is an unknown function $\mathbb C ^ {n \times n} \to \mathbb C ^ {n \times n}$ of the form $$ X \mapsto B^{-1} (X - A) (D B^{-1} (X - A) + C)^{-1} $$ for some $A, B, C, D \in \mathbb C ^ {n \times n}$ with $B,C$ invertible.

1. What is the minimum number of pairs $(X_i, f(X_i))$ needed to determine $f$?
2. Given such a list of pairs $(X_1, f(X_1)), \dots, (X_k, f(X_k))$ and an $X$, how does one compute $f(X)$?

I fear this problem may be too simple for MathOverflow, but it lies outside my area of expertise and I will accept a reference to somewhere dealing with this sort of problem. Thank you.

Answer 1

I would imagine that genericity/dimension count might suffice? If you wrote out $A, B^{-1}, C, D$, into their $n \times n$ components (thus $4n^2$ of these), then $f(X_i) = X_i$ is each a set of polynomials, equating component-wise, in the $4n^2$ variables (clearing out the denominator as well). Flattening the whole thing is a set of $n^2$ equations in $4n^2$ variables, i.e., an affine algebraic variety over the complexes. Generically, you will need 4 of these equations so as to have $4n^2$ variables and $4n^2$ defining polynomials, to give generic dimension 0. There could, of course, be multiple solutions (the number of expected solutions is generically given by Bezout's theorem). So, in short, I think you will need 4 pairs of points $(X_i, f(X_i))$ to solve all the components (there should be multiple solutions).

Answer 2

We have a black box $f:X\mapsto B^{-1}(X-A)(DB^{-1}(X-A)+C)^{-1}$.

We are looking for approximations of $A,B,C,D\in M_n$, where $A,B,C$ are invertible.

Note that if $(A,B,C,D)$ is a solution, then $(A,u B,\dfrac{1}{u}C,D)$ too, where $u\in\mathbb{C}^*$.

$\textbf{Step 1.}$ Note that we have also the black box $X\mapsto g(X)=f(X)^{-1}=D+C(X-A)^{-1}B$.

We use the following two calls to the black box with $X=\infty,X=0_n$,

practically $g(10^{20}RandomMatrix(n))\approx D,g(0_n)=D-CA^{-1}B$.

Thus we know $D$ and $CA^{-1}B$.

Thus we have the blackbox $h:X \mapsto (g(X)-D)^{-1}+(CA^{-1}B)^{-1}=B^{-1}XC^{-1}$.

In other words, $h=B^{-1}\otimes C^{-T}=U\otimes V$ (One stacks a vector into a matrix row by row), and it remains to obtain approximations of $U,V$.

$\textbf{Step 2.}$ The decomposition of a non-zero $h$ into a tensor is unique, up to a factor: if $(U,V)$ is a solution, then the other solutions are in the form $(\lambda U,\dfrac{1}{\lambda}V)$, where $\lambda\in\mathbb{C}^*$ -we get back to the non-uniqueness of $B,C$ in the original problem-.

Note that the algebraic equations $UX_iV^T=h(X_i)$, in the unknowns $(u_{i,j}),(v_{i,j})$, have degree $2$ but no longer contain denominators like the previous ones associated to $f,g$.

To obtain the $2n^2-1$ unknowns, we must call the blackbox at least $2$ times.

Unfortunately, if we randomly choose the $(X_i)_{i\leq 2}$, then, in general, that does not work.

Using the Maple's command "fsolve" we have performed numerical tests -for $n\leq 5$-. That "shows" that if we randomly choose $3$ matrices $(X_i)_{i\leq 3}$, then we obtain always an approximation of "the" solution.

Yet, the software "fsolve" is not very powerfull; we get the solution much faster if we make $4,5$ or $6$ calls to the black box.

$\textbf{Conclusion.}$ Above is exposed a method allowing to calculate approximations of $A,B,C,D$ using at least $5$ calls to the black box. Obviously, when $n$ increases, it is necessary to increase the number of calls.

Answer 3

Not an answer, but the formula is too wide for a comment.

Why didn't you say that $f(X)$ is an entry of an inverse matrix $$\begin{pmatrix} X-A & -B \\ - C & -D \end{pmatrix}^{-1}=\begin{pmatrix} \cdot & \cdot \\ \cdot & -f(X) \end{pmatrix} \qquad ?$$