26
$\begingroup$

This question was motivated by a recent MO post. You know $n$ elements of the $N\times N$ matrix $M$ and you do not know $n$ elements of the inverse $M^{-1}$ (but you know the other $N^2-n$ elements of $M^{-1}$). Equating $(M^{-1})^{-1}=M$ gives $n$ nonlinear equations in $n$ unknowns, which in general will have multiple solutions. Under which additional condition can one reconstruct the matrix $M$ uniquely? Does it matter where in the matrix are the $n$ elements located?

Conjecture: A positive definite $N\times N$ matrix is uniquely determined by its diagonal elements and by the off-diagonal elements of its inverse.

For $N=2$ it is true,$^\ast$ and some experimentation$^{\ast\ast}$ for larger $N$ suggests it is true for all $N$.


$^\ast$ For $N=2$ one has $M = \begin{pmatrix}a & b \\ b & c \end{pmatrix}$, $M^{-1} = \frac{1}{a c - b^2} \begin{pmatrix}c & -b \\ -b & a \end{pmatrix}$, we know $a,c$ and we know $\beta=b/(ac−b^2)$. There are two solutions for the unknown $b$, $b_\pm=(\pm\sqrt{4ac\beta^2+1}−1)/2\beta$, only $b_+$ gives a positive definite $M$.

$^{\ast\ast}$ Mathematica test for $N=3,4,5$, when there are, respectively, up to $5,14,22$ solutions for the unknown matrix elements, but only one of these gives a positive definite $M$.

$\endgroup$
11
  • 1
    $\begingroup$ I hesitated whether to raise this as a follow-up of the cited MO post, but following this advice I ask it separately. $\endgroup$ Oct 22, 2021 at 17:06
  • $\begingroup$ Over what field are the entries? Are you asking about all fields? $\endgroup$
    – joro
    Oct 23, 2021 at 5:56
  • $\begingroup$ one can take $M$ real symmetric (in the linked post it is a covariance matrix). $\endgroup$ Oct 23, 2021 at 7:09
  • $\begingroup$ Perhaps you mean your conjecture to be "$n = N$ elements on the diagonal and $N^2 - n = N^2 - N$ off diagonal elements"? Otherwise already for $N = 2$, giving the two diagonal elements of $M^{-1}$ only determines the off diagonal element of $M$ up to sign. $\endgroup$
    – Random
    Oct 23, 2021 at 15:28
  • $\begingroup$ Actually, the conjecture is false for $N = 2$. $\endgroup$
    – Random
    Oct 23, 2021 at 15:30

2 Answers 2

30
+50
$\begingroup$

The conjecture is true. More precisely, here is what I will prove:

Theorem Partition $\{ (i,j) : 1 \leq i \leq j \leq n \}$ into two disjoint sets, $A \sqcup B$. Let $X$ and $Y$ be positive definite $n \times n$ matrices and suppose that $X_{ij} = Y_{ij}$ for $(i,j) \in A$ and $(X^{-1})_{ij} = (Y^{-1})_{ij}$ for $(i,j) \in B$. Then $X = Y$.

Lemma 1 Consider the function $f(M) = \log \det(M)$ on the space of $n \times n$ matrices $M$ with positive determinant. Then we can think of the gradient, $\nabla(f)$, as an $n \times n$ matrix as well. In this sense, we have $\nabla(f)|_M = (M^{-1})^T$.

Proof: Let $E_{ij}$ be the matrix with a $1$ in position $(i,j)$ and $0$'s everywhere else. Then $\nabla(f)_{ij} = \tfrac{d}{dt} \log \det(M+t E_{ij})$. This is $\tfrac{1}{\det(M)} \ \tfrac{d\ \det(M+t E_{ij})}{dt} = \tfrac{1}{\det(M)} \cdot (-1)^{i+j} \det \widehat{M_{ij}}$. Here $\widehat{M}_{ij}$ is the $(n-1) \times (n-1)$ matrix where we delete row $i$ and column $j$. Using the formula for the inverse matrix in terms of the adjugate matrix, we see that $\nabla(f)_{ij} = (M^{-1})_{ji}$. $\square$

Lemma 2 The function $f$ is strictly concave on the cone of positive definite matrices.

Proof Let $P$ be a positive definite matrix and let $Q$ be a symmetric matrix. We will show that $f(P+tQ)$ is concave for small $t$.

Since $P$ is positive definite, we can factor $P = ZZ^T$ for some invertible $Z$. Then $\log \det(P+Q t) = \log P + \log \det (\mathrm{Id} + t Z^{-1} Q (Z^{-1})^T)$. Since $Z^{-1} Q (Z^{-1})^T$ is symmetric, it is diagonalizable, say with eigenvalues $\lambda_1$, $\lambda_2$, ..., $\lambda_n$. So $\log \det (\mathrm{Id} + t Z^{-1} Q (Z^{-1})^T) = \sum \log (1+t \lambda_i)$. As long as $|t| < \min(|\lambda_i|^{-1})$, this is a sum of concave functions. $\square$

Now, let $A$, $B$, $X$ and $Y$ be as in the statement of the theorem. Let $V = \mathrm{Span}_{(i,j) \in B} (E_{ij}+E_{ji})$.

The condition that $X_{ij} = Y_{ij}$ for $(i,j) \in A$ means that $Y$ is in the affine space $X+V$.

From Lemma 1, the condition that $(X^{-1})_{ij} = (Y^{-1})_{ij}$ for $(i,j) \in B$ means that $f$, when restricted to the affine space $X+V$, has the same gradient at $X$ and at $Y$.

Now, the space of positive definite matrices is convex, so its intersection with the affine space $X+V$ is convex, so we can draw a line segment from $X$ to $Y$ and the line segment will stay in the space of positive definite matrices. By Lemma 2, our function $f$ restricted to this line segment will be strictly concave. But by our observation in the previous paragraph, this function has the same derivative at $X$ and at $Y$. This is only possible if the line segment has length $0$, so $X=Y$. $\square$


This was a uniqueness result. I will now prove an existence result. Let $A$ and $B$ be as above, and let $P$ and $Q$ be positive definite matrices. I will now show that there is positive definite matrix $X$ with $X_{ij} = P_{ij}$ for $(i,j) \in A$ and $(X^{-1})_{ij} = Q_{ij}$ for $(i,j) \in B$.

As above, let $V=\mathrm{Span}_{(i,j) \in B} (E_{ij}+E_{ji})$. Let $K$ be the intersection of the affine space $P+V$ with the cone of positive definite matrices. Let $g(X) = \log \det X - \mathrm{Tr}(QX)$. We will show that there is a point $X$ in $K$ where $\nabla(g)=0$. Since $X \in K$, the matrix $X$ is positive definite with $X_{ij} = P_{ij}$ for $(i,j) \in A$. By the computations in the first part, the equation $\nabla(g)=0$ shows that $(X^{-1})_{ij} = Q_{ij}$.

So we are reduced to the goal of showing that $g$ has a local maximum in $K$. Fortunately, $P \in K$, so $K$ is nonempty. Unfortunately, $K$ is not compact. So we need to replace it by a compact version. Let $\overline{K}$ be the set of positive semi-definite matrices in $P+V$. So $\overline{K}$ is closed, but not yet compact.

Lemma There is a constant $c>0$ such that, for all positive definite matrices $X$, we have $|X| \leq c \mathrm{Tr}(QX)$, where $|X|$ is the Frobenius norm.

Proof The statement of the Lemma is invariant under conjugating $Q$ and $X$ by an orthogonal matrix, so we may assume that $Q$ is diagonal, with diagonal entries $0 < q_1 < q_2 < \cdots < q_n$. So $$\mathrm{Tr}(QX)= \sum_i q_i X_{ii} \geq q_1 \sum_i X_{ii}.$$ We also have $$|X| = \sqrt{ \sum_{i,j} X_{ij}^2} \leq \sqrt{\sum_{i,j} X_{ii} X_{jj}} = \sum_i X_{ii}.$$ (We have used that $X$ is positive definite to deduce the Cauchy-Schwartz inequality $X_{ij}^2 \leq X_{ii} X_{jj}$.) So we can take $c=q_1$. $\square$.

Now, if the eigenvalues of $X$ are $\lambda_1$, $\lambda_2$, \dots, $\lambda_n$, then $\det(X) = \prod \lambda_i$ and $|X| = \sqrt{\sum \lambda_i^2}$ so we have $\det(X) \leq |X|^n$ and thus $\log \det(X) \leq n \log |X| \leq n (\log \mathrm{Tr}(QX)+\log c)$. So $g(X)$ is bounded above by $n \log \mathrm{Tr}(QX) - \mathrm{Tr}(QX) + n \log c$.

We have $\lim_{z \to \infty} n \log z - z=- \infty$ so, if $\mathrm{Tr}(QX) \to \infty$ then $g(X) \to - \infty$. Thus, we can choose some large $M$ such that the value of $g$ at $P$ is larger then its value on the half space $\{ X : \mathrm{Tr}(QX) \geq M \}$.

Now, consider the function $X$ on $\overline{K} \cap \{ X : \mathrm{Tr}(QX) \leq M \}$. This, finally, is a compact set, so $g$ achieves a maximum somewhere on it. The maximum is not at the positive semidefinite points, since $g$ is $-\infty$ there, and it is not on the hyperplane $\{\mathrm{Tr}(QX) = M \}$ by the choice of $M$. So the maximum is in the interior and we win. $\square$


UPDATE: I recently talked with Piotr Zwiernik and Thomas Kahle about this question, and they explained to me that this is a special case of a 1978 theorem of Barndorff-Nielsen which goes by the name "Variational Independence". From their perspective, this has nothing to do with matrices or inverses, it is solely a theorem of convex analysis. I'll do my best to explain the Variational Independence theorem. Thanks to Piotr and Thomas for their help; of course, all errors are mine.

Let $V$ be a finite dimensional real vector space, $C$ an open convex subset of $V$ and $f$ a $C^1$ strictly convex function $C \to \mathbb{R}$ with the property that $|\nabla(f)(x)| \to \infty$ as $x$ approaches any point in $\partial C$. Such a pair $(C,f)$ is called "of Legendre type".

In our application, $V$ will be symmetric matrices, $C$ will be positive definite symmetric matrices and $f$ will be $f(X) = - \log \det(X)$, so $\nabla(f)(X) = - X^{-1}$.

Let $V^{\ast}$ be the dual vector space to $V$, so $\nabla(f)$ takes values in $V^{\ast}$. Let $C^{\ast} = \nabla(f)(C)$. Then $C^{\ast}$ is an open convex set and $\nabla(f): C \to C^{\ast}$ is bijective. For $x^{\ast} \in C^{\ast}$, define $f^{\ast}(x^{\ast}) = \min_{x \in C} f(x) - \langle x^{\ast}, x \rangle$; this is known as the Legendre conjugate of $f$. Then the pair $(C^{\ast}, f^{\ast})$ is also of Legendre type, and $\nabla(f^{\ast})$ is the inverse bijection $C^{\ast} \to C$. See Chapter 5, Section 26, of Rockafellar for the technical details here.

Now, suppose that we have a short exact sequence of vector spaces $0 \to B \overset{\beta}{\longrightarrow} V \overset{\alpha}{\longrightarrow} A \to 0$, so that we get a dual sequence $0 \to A^{\ast} \overset{\alpha^{\ast}}{\longrightarrow} V^{\ast} \overset{\beta^{\ast}}{\longrightarrow} B^{\ast} \to 0$. In our setting; $A$ and $B$ will be the symmetric matrices supported on the coordinates indexed by the disjoint sets $A$ and $B$ (which is why I reused the notation), so $\alpha(X)$ and $\beta^{\ast} \nabla(f)(X)$ are the projections of $X$ and $X^{-1}$ onto the $A$ and $B$ coordinates respectively.

The "variational independence" theorem is that the map $$x \mapsto (\alpha(x), \beta^{\ast} \nabla(f)(x))$$ is always a bijection between $C$ and $\alpha(C) \times \beta(C^{\ast})$.

See Theorem 5.34 in Barndorff-Nielsen for the original proof, and see Section 5.1 in Zwiernik for a very accessible discussion, including the current application and related transformations.

$\endgroup$
10
  • 1
    $\begingroup$ I am deeply impressed. $\endgroup$ Nov 2, 2021 at 9:15
  • $\begingroup$ existence --- uniqueness --- well done, in my world this would be stuff for a publication, but perhaps MO suffices. $\endgroup$ Nov 3, 2021 at 7:19
  • $\begingroup$ I have been wondering if this is publishable. I agree that the significance is high enough, the problem is originality. I suspect that a natural question like this must have been answered before, but I don't know where to look for it. I'm going to start poking around in the algebraic statistics literature, and then looking for people to ask. $\endgroup$ Nov 3, 2021 at 10:55
  • 2
    $\begingroup$ One of the reasons that MO is more fun than regular research is that, when I solve an interesting question, I am not required to look for previous work before I get credit for it. $\endgroup$ Nov 3, 2021 at 10:55
  • 1
    $\begingroup$ one previous work could be Positive Definite Completions of Partial Hermitian Matrices $\endgroup$ Nov 3, 2021 at 11:22
5
$\begingroup$

Too long for a comment of Barndorff-Nielsen's Variational Independence. It turns out to be important for Continuum Physics, more precisely in Thermodynamics.

One considers a field $(t,x_1,\ldots,x_d)\mapsto u=(u_1,\ldots,u_n)$, taking values in an open convex subset $O$. It is governed by a (first-order PDE) system of conservation laws $$ \partial_tu+\sum_1^d\partial_{x_\alpha}f^\alpha(u)=0. $$ A typical example is that of the Euler equations in inviscid gas dynamics, where we neglect heat diffusion. Here $n=d+2$ and the coordinates of $u$ consist in mass density $\rho$, linear momentum $\rho v$ ($v=(v_1,\ldots,v_d)$ is the fluid velocity) and the mechanical energy $$E=\frac12\rho|v|^2+\rho e.$$ Hereabove, $e$ is the internal energy per unit mass. The PDEs express the local conservation of mass, momentum and energy.

Thermodynamics assumes that such a system is compatible with an additional conservation law $$\partial_t\eta(u)+{\rm div}_x\vec q(u)=0,$$ where $\eta$ is a strictly convex function, which we call the entropy of the system. Mind that physicists prefer a concave entropy; mathematicians' entropy is just the opposite. Actually the compatibility is valid only for Lipschitz continuous fields $u$ (reversible processes), because it involves the chain rule. Irreversible processes are instead constrained by the inequality $$\partial_t\eta(u)+{\rm div}_x\vec q(u)\le0,$$ understood in the distributional sense.

An important fact is that the existence of such a strictly convex entropy implies that the system of PDEs is symmetric hyperbolic in suitable coordinates (Lax & Friedrichs, Godunov), and therefore the Cauchy problem is well-posed, at least locally in time, for suitably regular initial data (Leray, Garding).

Now let us go back to the matter of the MO question. Let us choose some coordinates, say $U:=(u_1,\ldots,u_r)$. We wish to discard the remaining ones $(u_{r+1},\ldots,u_n)$, while freezing the "dual" coordinates $$ \frac{\partial\eta}{\partial u_{r+1}}=a_{r+1},\ldots,\frac{\partial\eta}{\partial u_n}=a_n, $$ where $a_{r+1},\ldots,a_n$ are given constants. Because $$u\mapsto \left(u_1,\ldots,u_r,\frac{\partial\eta}{\partial u_{r+1}},\ldots,\frac{\partial\eta}{\partial u_n}\right)$$ is one-to-one, we may write any function $g(u)$ as $\widetilde{g}(u_1,\ldots,u_r)$ over the level set defined by $\vec a$ . This allows us to define a so-called reduced system $$ \partial_tU+\sum_1^d\partial_{x_\alpha}F^\alpha(u)=0, $$ where $F^\alpha_j=\widetilde{f^\alpha_j}$ for $j=1,\ldots,r$. Notice that we retained only the $r$ first lines of the original system.

Now the Theorem: The reduced system admits too a strictly convex entropy $\eta_*$, obtained in the following way. Consider the Legendre transform $\hat\eta$, which is defined over $\nabla\eta(O)$. Take its restriction to the convex set $$\nabla\eta(O)\bigcap\{z\,;\,z_{r+1}=a_{r+1},\ldots,z_n=a_n\}.$$ Then take back the Legendre transform $\eta_*$ of this restriction, noticing that this is a function of $u_1,\ldots,u_r$.

One consequence of the theorem is that the reduced system is symmetrizable too, hence hyperbolic. The other one is that it gives a procedure to find the entropy of the reduced system.

Application to Gas dynamics: here $\eta=-\rho s$ and $s=s(\rho,e)$ is the (physical) entropy per unit mass. The latter satisfies the Gibbs identity $$\theta ds=de+pd\frac1\rho,$$ $p(\rho,e)$ being the pressure. Let us choose $r=d+1$, noticing that $r+1=n$ (we discard only one coordinate and one conservation law) and $u_n=E$. One easily checks that $$\frac{\partial\eta}{\partial E}=-\frac1\theta,$$ so that the reduced system is just isothermal dynamics. Amazingly, the reduced entropy $\eta_*$ is just the mechanical energy !

$\endgroup$
1
  • 1
    $\begingroup$ Beautiful. Thanks. $\endgroup$ Oct 13, 2023 at 13:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.