I'm trying to use the log-determinant to regularize an optimization problem. To make the argument work, I need to bound the second derivative of the log-determinant.

I need to prove that $\text{Tr}\left( \left(A^{-1} B\right)^2\right) \geq 1$ whenever:

  1. $A$ is positive semidefinite
  2. $B$ is symmetric, has zeroes on the diagonal, and has at least one entry which is $\geq 1$.
  3. The diagonal entries of $A$ are 1.

From messing around a bit it seems like in fact there are always unit vectors $v, w$ such that $v^T A^{-1} B w \geq 1$---for example, this is true if B has only a single large entry, or if A and B commute. That would imply the conclusion and seems like it should be easy enough to confirm or deny, but I'm stumped.

Any thoughts?

  • $\begingroup$ By "positive" you mean "positive definite"? $\endgroup$ Mar 25, 2013 at 6:41
  • $\begingroup$ A is not assumed to be symmetric, is it? $\endgroup$ Mar 25, 2013 at 7:43
  • $\begingroup$ A is positive, thus symmetric. The problem is invariant under the $GL(n)$-action $X\mapsto g^T.X g$ for $g\in GL(n)$. Any $g$ is of the form $g=n.a.k$ where $n$ is lower triangular with 1's on the diagonal, $a$ is diagonal with positive entries, and $k$ is orthogonal (Gram-Schmidt or Iwasawa). Choose $a=I$ so to not mess up too much your assumptions. There is an $n$ such that $n^T.A.n$ is diagonal with positive entries. Compute this entries. Check $n^t.B.n$. I hope this helps. $\endgroup$ Mar 25, 2013 at 8:32
  • $\begingroup$ About the entry of $B$ larger than $1$, is it diagonal ? $\endgroup$ Mar 25, 2013 at 9:23
  • $\begingroup$ Sorry for the ambiguity, A is positive semidefinite (and symmetric). The large entry of B is not necessarily on the diagonal. Also, note that the claim is easy by rote computation if B has only one large entry. This is the observation that inspired me to try to prove this bound (that, and hope). Peter: I don't see how to use the large entry of B after making such a transformation. Does this translate into some nice property of $n^T B n$ or $g^T B g$? $\endgroup$ Mar 25, 2013 at 18:57

1 Answer 1


Here is an argument based on convex optimization.

Consider the case where $B$ has a one on the diagonal and the rest of the matrix is arbitrary. Without loss of generality, we can assume that $b_{11}=1$. Thus, we can write the general matrix $B=E+C$, where $E=e_1e_1^T$ with $e_1=(1,0,\ldots,0)$ being the first canonical basis vector, and $C$ is a symmetric matrix with $C_{11}=0$.

(Note: If the entry $\ge 1$ is an off-diagonal, then we can write $B=e_ie_j^T+e_je_i^T$, and run an argument similar to the one below---this one is somewhat more tedious so I did not work it out).

To save on typing, first define the notation: $\DeclareMathOperator{\vect}{vec}$

\begin{equation*} Z = A^{-1},\quad M = Z \otimes Z,\quad e=\vect(E)\quad c=\vect(C). \end{equation*}

Then, the trace under question is: \begin{equation*} \mbox{trace}(Z(E+C)Z(E+C)) = e^TMe + c^TMc + 2c^TMe. \end{equation*} Actually, we have $(Kc)^TMc$ as the second term, where $K$ is the commutation matrix, but after some simplifications, it will turn out that we can drop $K$.

Now, we minimize $c^TMc + 2c^TMe$ subject to $c^Te=0$ (and the constraint that $Kc=c$ to ensure symmetry, but this constraint can be eliminated, so I've dropped it).

Introduce the Lagrange multiplier $\nu$ corresponding to the constraint $c^Te=0$, the first-order optimality conditions for this convex optimization problem are: \begin{equation*} 2Mc + 2Me - \nu e = 0,\qquad c^Te=0. \end{equation*}

Thus, we have \begin{eqnarray*} Mc &=& (\nu/2) e - Me\\\\ c &=& (\nu/2) M^{-1}e - e\\\\ &\implies& c^Te = (\nu/2) e^TM^{-1}e - e^Te\\\\ &\implies& \nu=2\qquad\text{since}\ e^TM^{-1}e=1. \end{eqnarray*}

Thus, in particular, an optimum $c$ must satisfy \begin{equation*} c = M^{-1}e - e, \end{equation*} from which it follows that $e^TMc = 1 - e^TMe$ and $c^TMc=0-c^TMe$. Thus, the objective is \begin{equation*} c^TMc + 2c^TMe= c^TMe = 1 - e^TMe, \end{equation*} from it immediately follows that \begin{equation*} \mbox{trace}(Z(E+C)Z(E+C)) = e^TMe + c^TMc + 2c^TMe \ge 1. \end{equation*}


Your Answer

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

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