Appropriate measure to find smallest covariance matrix In the textbook I am reading they use positive definiteness (semi-positive definiteness) to compare two covariance matrices. The idea being that if $A-B$ is pd then $B$ is smaller than $A$. But I'm struggling to get the intuition of this relationship?
There is a similar thread here:
https://math.stackexchange.com/questions/239166/what-is-the-intuition-for-using-definiteness-to-compare-matrices
What is the intuition for using definiteness to compare matrices?
Although the answers are nice they don't really address the intuition.
Here is an example I find confusing:
\begin{equation}
\begin{bmatrix} 16 & 12 \\ 12 & 9 \end{bmatrix} - \begin{bmatrix} 1 & 2 \\ 2 & 4 \end{bmatrix}
\end{equation}
now here the determinant of the difference is -25 so the relation is not pd or even psd and so the first matrix is not greater than the first?
I simply want to compare two 3*3 covariance matrices to see which is smallest? It would seem more intuitive to me to use the something like the euclidean norm to compare them? However this would mean that the first matrix above is greater than the second matix. Moreover I only ever see the pd/psd criterion used to compare covariance matrices.
Can someone explain why pd/psd is better than using another measure such as the euclidean norm?
I have also posted this question on the math forum (wasn't sure what was best) hope this does not contravene any rules.
https://math.stackexchange.com/questions/628135/comparing-two-covariance-matrices
 A: @kjetil b halvorsen gives a nice discussion of the geometric intuition behind positive semi-definiteness as a partial ordering.  I'll give a more grubby-handed take on that same intuition.  One which proceeds from what sorts of calculations you might like to do with your variance matrixes.
Suppose you have two random variables $x$ and $y$.  If they are scalars, then we can calculate their variances as scalars, and compare them in the obvious way using the scalar real numbers $V(x)$ and $V(y)$.  So if $V(x)=5$ and $V(y)=15$, we say that the random variable $x$ has a smaller variance than does $y$.
On the other hand, if  $x$ and $y$ are vector-valued random variables (let's say they are two-vectors), how we compare their variances is not so obvious.  Say their variances are:
\begin{align}
V(x) = \left[ \begin{array}{c c} 1 & 0.5 \\ 0.5 & 1 \end{array} \right] \qquad
V(y) = \left[ \begin{array}{c c} 8 & 3 \\ 3 & 6 \end{array} \right]
\end{align}
How do we compare the variances of these two random vectors?  One thing we could do is just compare the variances of their respective elements.  So, we can say that the variance of $x_1$ is smaller than the variance of $y_1$ by just comparing real numbers, like:  $V(x_1)=1<8=V(y_1)$ and $V(x_2)=1<6=V(y_2)$.  So, maybe we could say that the variance of $x$ is $\le$ the variance of $y$ if the variance of each element of $x$ is $\le$  the variance of the corresponding element of $y$.  This would be like saying $V(x) \le V(y)$ if each of the diagonal elements of $V(x)$ is $\le$ the corresponding diagonal element of $V(y)$.
This definition seems reasonable at first blush.  Furthermore, as long as the variance matrixes we are considering are diagonal (i.e. all covariances are 0), it is the same as using semi-definiteness.  That is, if the variances look like
\begin{align}
V(x) = \left[ \begin{array}{c c} V(x_1) & 0 \\ 0 & V(x_2) \end{array} \right] \qquad
V(y) = \left[ \begin{array}{c c} V(y_1) & 0 \\ 0 & V(y_2) \end{array} \right]
\end{align}
then saying $V(y)-V(x)$ is positive-semi-definite (i.e. that $V(x) \le V(y)$) is just the same as saying $V(x_1) \le V(y_1)$ and $V(x_2) \le V(y_2)$.  All seems good until we introduce covariances.  Consider this example:
\begin{align}
V(x) = \left[ \begin{array}{c c} 1 & 0.1 \\ 0.1 & 1 \end{array} \right] \qquad
V(y) = \left[ \begin{array}{c c} 1 & 0 \\ 0 & 1 \end{array} \right]
\end{align}
Now, using a comparison which only considers the diagonals, we would say $V(x) \le V(y)$, and, indeed, it's still true that element-by-element $V(x_k) \le V(y_k)$.  What might start to bother us about this is that if we calculate some weighted sum of the elements of the vectors, like $3x_1 + 2x_2$ and $3y_1 + 2y_2$, then we run into the fact that $V(3x_1 + 2x_2) \gt V(3y_1 + 2y_2)$ even though we are saying $V(x) \le V(y)$.
This is weird, right?  When $x$ and $y$ are scalars, then $V(x) \le V(y)$ guarantees that for any fixed, non-random $a$, $V(ax) \le V(ay)$.
If, for whatever reason, we are interested in linear combinations of the elements of the random variables like this, then we might want to strengthen our definition of $\le$ for variance matrixes.  Maybe we want to say $V(x) \le V(y)$ if and only if it is true that $V(a_1x_1 + a_2x_2) \le V(a_1y_1 + a_2y_2)$, no matter what fixed numbers $a_1$ and $a_2$ we pick.  Notice, this is a stronger definition than the diagonals-only definition since if we pick $a_1=1,a_2=0$ it says $V(x_1) \le V(y_1)$, and if we pick $a_1=0,a_2=1$ it says $V(x_2) \le V(y_2)$.
This second definition, the one which says $V(x) \le V(y)$ if and only if $V(a'x) \le V(a'y)$ for every possible fixed vector $a$, is the usual method of comparing variance matrixes based on positive semi-definiteness:
\begin{align}
V(a'y) - V(a'x) = a'V(x)a - a'V(y)a = a'\left(V(x) - V(y) \right)a
\end{align}
Look at the last expression and the definition of positive semi-definite to see that the definition of $\le$ for variance matrixes is chosen exactly to guarantee that $V(x) \le V(y)$ if and only if $V(a'x) \le V(a'y)$ for any choice of $a$, i.e. when $\left( V(y)-V(x) \right)$ is positive semi-definite.
So, the answer to your question is that people say a variance matrix $V$ is smaller than a variance matrix $W$ if $W-V$ is positive semi-definite because they are interested in comparing the variances of linear combinations of the elements of the underlying random vectors.  What definition you choose follows what you are interested in calculating and how that definition helps you with those calculations.
A: The ordering of matrices you refer to is known as the Loewner order and is a partial order much used in the study of positive definite matrices. A book-length treatment of the geometry on the manifold of positive-definite (posdef) matrices is here. 
I will first try to address your question about intuitions. A (symmetric) matrix $A$ is posdef if $c^T A c\ge 0$ for all $c \in \mathbb{R}^n$. If $X$ is a random variable (rv) with covariance matrix $A$, then $c^T X$ is (proportional to) its projection on some one-dim subspace, and $\mathbb{Var}(c^T X) = c^T A c$. Applying this to $A-B$ in your Q, first: it is a covariance matrix, second: A random variable with covar matrix $B$ projects in all directions with smaller variance than a rv with covariance matrix $A$. This makes it intuitively clear that this ordering can only be a partial one, there are many rv's which will project in different directions with wildly different variances.  Your proposal of some Euclidean norm do not have such a natural statistical interpretation. 
Your "confusing example" is confusing because both matrices have determinant zero. So for each one, there is one direction (the eigenvector with eigenvalue zero) where they always projects to zero. But this direction is different for the two matrices, therefore they cannot be compared. 
The Loewner order is defined such that $A \preceq B$,  $B$ is more positive definite than $A$, if $B-A$ is posdef.  This is a partial order, for some posdef matrices neither $B-A$ nor $A-B$ is posdef. An example is: 
$$
A=\begin{pmatrix} 1 & 0.5 \\ 0.5 & 1 \end{pmatrix}, \quad B= \begin{pmatrix} 0.5 & 0\\ 0 & 1.5 \end{pmatrix}
$$
One way of showing this graphically is drawing a plot with two ellipses, but centered at the origin, associated in a standard way with the matrices (then the radial distance in each direction is proportional to the variance of projecting in that direction):

In these case the two ellipses are congruent, but rotated differently (in fact the angle is 45 degrees). This corresponds to the fact that the matrices $A$ and $B$ have the same eigenvalues, but the eigenvectors are rotated. 
As this answer depends much on properties of ellipses, the following What is the intuition behind conditional Gaussian distributions?  explaining ellipses geometrically, can be helpful.
Now I will explain how the ellipses associated to the matrices are defined. A posdef matrix $A$ defines a quadratic form $Q_A(c) = c^T A c$. This can be plotted as a function, the graph will be a quadratic. If $A \preceq B$ then the graph of $Q_B$ will always be above the graph of $Q_A$.  If we cut the graphs with a horizontal plane at height 1, then the cuts will describe ellipses (that is in fact a way of defining ellipses). This cut ellipses are the given by the equations
$$ Q_A(c)=1, \quad Q_B(c)=1$$
and we see that $A \preceq B$ corresponds to the ellipse of B (now with interior) is contained within the ellipse of A. If there is no order, there will be no containment. We observe that the inclusion order is opposite to the Loewner partial order, if we dislike that we can draw ellipses of the inverses. This because $A \preceq B$ is equivalent to $B^{-1} \preceq A^{-1}$. But I will stay with the ellipses as defined here. 
An ellipse can be describes with the semiaxes and their length. We will only discuss $2\times 2$-matrices here, as they are the ones we can draw ... So we need the two principal axes and their length. This can be found, as explained here with an eigendecomposition of the posdef matrix. Then the principal axes are given by the eigenvectors, and their length $a,b$ can be calculated from the eigenvalues $\lambda_1, \lambda_2$ by
$$
a = \sqrt{1/\lambda_1}, \quad b=\sqrt{1/\lambda_2}.
$$
We can also see that the area of the ellipse representing $A$ is $\pi a b= \pi \sqrt{1/\lambda_1}\sqrt{1/\lambda_2} = \frac{\pi}{\sqrt{\det A}}$.
I will give one final example where the matrices can be ordered: 

The two matrices in this case were:
$$A =\begin{pmatrix}2/3 & 1/5 \\ 1/5 & 3/4\end{pmatrix}, \quad B=\begin{pmatrix}
1& 1/7 \\ 1/7& 1 \end{pmatrix} $$
