5
$\begingroup$

Suppose I have two quadratic forms on $\mathbb R^n$, represented as symmetric matrices $A$ and $B$ on the usual basis. I am interested in approximating the function $x \mapsto \max(x^TAx, x^TBx)$ while remaining within the space of quadratic forms.

Is there a nice way to define a "maximum" operation on symmetric matrices, such that $C = \max(A,B)$ if $C$ is, in some sense, the "smallest" symmetric matrix satisfying $x^TCx \ge x^TAx$ and $x^TCx \ge x^TBx$ for all vectors $x$?

I've purposely left the notion of the "smallest" matrix $C$ undefined, as I'll accept any formalization that allows its solution to be elegantly expressed and/or easily computed. One possibility is minimizing the trace of $C$. Another, if we restrict ourselves to positive semidefinite matrices, is minimizing a convenient matrix norm.

In any case, $\max$ certainly must be commutative, and must satisfy $\max(A,A) = A$. Also, if $A$ and $B$ share the same eigenvectors, with eigenvalues $\lambda_i$ and $\mu_i$ respectively, then it seems natural that $\max(A,B)$ should also have eigenvectors the same, and eigenvalues $\max(\lambda_i,\mu_i)$. Beyond that, I can't really tell.

  • 2
    Since $A-B$ is symmetric, we can write $A-B=\sum_{j=1}^n\alpha_jv_jv_j^{T}$ where $\alpha_j$ are real numbers and $v$ is a vector. We put $|A-B|:=\sum_{j=1}^n|\alpha_j|v_jv_j^T$ and $\max(A,B)=\frac 12(A+B+|A-B|)$.2012-01-25
  • 0
    Wow, that turned out to be much simpler than I expected! @Davide, it certainly looks like it satisfies all the criteria I wanted. Can you post it as an answer? Also, I'd guess you would need the $v_j$ to be orthonormal; is that not so?2012-01-25
  • 0
    In fact I think I managed to write it in a simpler way.2012-01-25
  • 0
    Rahul, your counterexample is right. However, you have a great answer from Davide.2012-01-25

1 Answers 1

5

Let $P$ an orthogonal matrix such that $P^T(B-A)P=\operatorname{diag}(\alpha_1,\ldots,\alpha_n)$. We define $|B-A|$ as the matrix such that $P^T|B-A|P=\operatorname{diag}(|\alpha_1|,\ldots,|\alpha_n|)$, namely $|B-A|=P\operatorname{diag}(|\alpha_1|,\ldots,|\alpha_n|)P^T$. We put $\max(A,B):=\frac 12\left(A+B+|A-B|\right)$. Then we have for a fixed $x\in\mathbb R^n$: \begin{align*} x^T\max(A,B)x-x^TAx&=\frac 12x^T(B-A+|A-B|)x\\ &=\frac 12x^T(P\operatorname{diag}(\alpha_1,\ldots,\alpha_n)P^T+P\operatorname{diag}(|\alpha_1|,\ldots,|\alpha_n|)P^T)x\\ &=\frac 12(P^Tx)^T(\operatorname{diag}(\alpha_1,\ldots,\alpha_n)+\operatorname{diag}(|\alpha_1|,\ldots,|\alpha_n|))P^Tx\\ &\geq 0 \end{align*} since $\operatorname{diag}(\alpha_1+|\alpha_1|,\ldots,\alpha_n+|\alpha_n|)$ is positive semidefinite. By the same way $$x^T\max(A,B)x-x^TBx=\frac 12(P^Tx)^T(\operatorname{diag}(-\alpha_1,\ldots,-\alpha_n)+\operatorname{diag}(|\alpha_1|,\ldots,|\alpha_n|))P^Tx\geq 0.$$

  • 1
    Perfect answer. By the way, I took the liberty of correcting "positive definite" to "positive *semi*definite" as $\alpha_i + \lvert\alpha_i\rvert$ can be zero.2012-01-25
  • 0
    Indeed, this matrix is only semi-definite in general, so it's was a good idea to correct it. By the way, this proof shows how to construct $\max(A,B)$ given $A$ and $B$.2012-01-25
  • 0
    Any idea if this operation would be associative? It certainly doesn't look like it at first glance, but then neither does $\max(x,y) = \frac12(x + y + |x-y|)$ on the real numbers, yet it is nonetheless.2012-01-27