22
$\begingroup$

The set of positive semidefinite symmetric real matrices form a cone. We can define an order over the set of matrices by saying $X\geq Y$ if and only if $X-Y$ is positive semidefinite. I suspect that this order does not have the lattice property, but I would still like to know which matrices are candidates for the meet and join of two matrices.

In other words, let $P$ be the cone of positive semidefinite matrices. Is there a nice characterization of the set $(X+P)\cap (Y+P)$, for two given matrices? What are the minimal points in this intersection?

$\endgroup$
  • 2
    $\begingroup$ To get started, one can look at orthogonal projections: for them there is a canonical notion of meet (projection onto the intersection of two ranges) and join (projection onto their linear span). Pushing a little further, one can write $aP\wedge bQ = \min(a,b)P\wedge Q$ and $aP\vee bQ = \max(a,b) P\vee Q$, where $a,b\ge 0$ and $P,Q$ are projections. I don't know how to extend this two sums of two projections. $\endgroup$ – 75064 May 7 '13 at 3:21
  • $\begingroup$ You're correct in your suspicion---this is a partial ordering that does not have the lattice property. I'll give some thought to the more general question. $\endgroup$ – Michael Grant May 17 '13 at 13:35
27
+100
$\begingroup$

Geometric Interpretation. Consider a positive definite matrix $A$. It defines the ellipsoid $${\cal E}_A = \{u: u^T A u \leq 1\}.$$ Note that the correspondence between $A$ and ${\cal E}_A$ is one-to-one. Moreover, $A\succeq B$ if and only if ${\cal E}_B$ contains ${\cal E}_A$. Using this fact, we can give the following characterization.

$C \succeq A$ and $C \succeq B$ if and only if ${\cal E}_C \subset {\cal E}_A \cap {\cal E}_B$.

Similarly,

$C \preceq A$ and $C \preceq B$ if and only if ${\cal E}_C \supset {\cal E}_A \cup {\cal E}_B$.

Now a matrix $C$ is a minimal matrix s.t. $C \succeq A$ and $C \succeq B$ if and only if ${\cal E}_C \subset {\cal E}_A \cap {\cal E}_B$ and there is no ellipsoid “sandwiched” between ${\cal E}_C$ and ${\cal E}_A \cap {\cal E}_B$. It is easy to see that that happens iff $\partial{\cal E}_C$ intersects $\partial{\cal E}_A$ by a $k$-dimensional ellipsoid and $\partial{\cal E}_C$ intersects $\partial{\cal E}_B$ by an $n-k$ dimensional ellipsoid. This can be stated in terms of matrices $A$, $B$, and $C$.

Consider a minimal $C$ s.t. $C \succeq A$ and $C \succeq B$. Then there are two subspaces $U$ and $V$ with ${\mathbb R}^n = U \oplus V$ such that $u^T Cu = u^T Au$ for $u\in U$ and $u^T Cu = u^T Bu$ for $u\in V$; in particular, $\operatorname{rank}(C-A) + \operatorname{rank}(C-B) \leq n$.

Visualization. The following animation shows ellipses ${\cal E}_C$ inscribed in ${\cal E}_A \cap {\cal E}_B$ in two dimensions. Every ellipse ${\cal E}_C$ corresponds to a minimal matrix $C$ ($C \succeq A$ and $C \succeq B$)

Ellipse ${\cal E}_C$ inscribed in ${\cal E}_A \cap {\cal E}_B$

And this animation shows minimum ellipses ${\cal E}_C$ containing ${\cal E}_A \cup {\cal E}_B$.

minimum ellipses ${\cal E}_C$ containing ${\cal E}_A \cup {\cal E}_B$

I'm afraid that there is no more explicit characterization of sets $\{C: C \succeq A \text{ and } C \succeq B\}$ and $\{C: C \preceq A \text{ and } C \preceq B\}$.

Correspondence between “meet” and “join” matrices. Note that if $C_1$ is a “join” then $C_2 = A+B-C_1$ is a “meet” and vice versa. That follows from the fact that $C_2 \preceq A$ iff $A+B-C_1 \preceq A$ iff $B \preceq C_1$; similarly, $C_2 \preceq B$ iff $A \preceq C_1$.

Characterization for $2\times 2$ matrices. If $A$ and $B$ are $2\times 2$ matrices (s.t. $A\not\preceq B$ and $A\not\succeq B$) then meet and join matrices $C$ must satisfy the following equations $\det(C-A) = 0$ and $\det(C-A) =0$. The set of symmetric matrices that satisfy this system of equations forms a one dimensional curve in the space of matrices. Let us write $$C_{xyz} = \begin{pmatrix}x&y\\y&z\end{pmatrix}.$$ Then the set
$$\{(x,y,z): \det(C_{xyz} - A) = \det(C_{xyz} - B) = 0\}$$ is a hyperbola (that lies in a plane in ${\mathbb R}^3$). Points on one branch of the hyperbola correspond to join matrices; points on the other branch correspond to meet matrices.

Notes. Note that by changing the basis we can always assume that $A=I$ and $B$ is a diagonal matrix, but I don't think that this observation leads to a very explicit characterization of $\{C: C \succeq A \text{ and } C \succeq B\}$. In particular, $C$ does not have to be a diagonal matrix. For example, let $$A=\begin{pmatrix} 1& 0\\0& 1\end{pmatrix}\quad B =\begin{pmatrix} 2& 0\\0& 1/2\end{pmatrix}.$$ Then the following matrices $C$ are minimal matrices greater ($\succeq$) than $A$ and $B$: $$C=\begin{pmatrix} 2& 0\\0& 1\end{pmatrix}\quad C=\begin{pmatrix} 3& 1\\1& 3/2\end{pmatrix} \quad C=\begin{pmatrix} 3& -1\\-1& 3/2\end{pmatrix}.$$ (The set of all such matrices $C$ forms a one dimensional curve in the space of all $2\times 2$ matrices.)

$\endgroup$
  • $\begingroup$ I'm pretty convinced that the minimal $C$ would have to exist on the flat that contains both $A$ and $B$ -- that is, if $A=I$ and $B$ is diagonal, that $C$ would have to be diagonal as well, with the same diagonal ordering as $B$. $\endgroup$ – Josephine Moeller May 18 '13 at 20:03
  • $\begingroup$ Yeah, the proof sketch would be something like, "the minimal $C$ has to be the largest ellipsoid contained in both $A$ and $B$ -- if $B$ is axis-aligned then $C$ must be too." $\endgroup$ – Josephine Moeller May 18 '13 at 20:13
  • 1
    $\begingroup$ @JohnMoeller, this is not correct. We can always assume that $A=I$ and $B$ is diagonal, but still minimal $C$ is not determined. Consider the 2-dimensional case. Let $A=I_2$ (${\cal E}_A$ is a circle) and $B = \mathrm{diag}(2,1/2)$ (${\cal E}_A$ is an ellipse that intersects ${\cal E}_A$). Start with $C= \mathrm{diag}(2,1)$. Let's rotate ${\cal E}_C$ and shrink/expand it along its axes so that it lies completely in ${\cal E}_A \cap {\cal E}_B$ and touches the boundary at 4 points. The matrix corresponding to the rotated ellipse will not be diagonal! $\endgroup$ – Yury May 18 '13 at 20:24
  • $\begingroup$ This argument shows that in the two dimensional case the set of minimal matrices $C$ is 1-dimensional. $\endgroup$ – Yury May 18 '13 at 20:24
  • 2
    $\begingroup$ Thank you for this answer! Thinking in terms of ellipsoids really helps in visualizing it, but you made it even easier with the animations. It seems to me that there may still be something to be said in terms of characterizing the "one-dimensional" curve, for the case of 2x2 matrices. Perhaps asking for an explicit characterization is too much, but maybe just checking some properties. For example, is there a one-to-one correspondence between members of the meet and join? $\endgroup$ – Henrique May 19 '13 at 16:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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