Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
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|)$. –  Davide Giraudo Jan 25 '12 at 12:45
    
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? –  Rahul Jan 25 '12 at 12:56
    
In fact I think I managed to write it in a simpler way. –  Davide Giraudo Jan 25 '12 at 12:59
    
Rahul, your counterexample is right. However, you have a great answer from Davide. –  emiliocba Jan 25 '12 at 13:25

1 Answer 1

up vote 4 down vote accepted

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.$$

share|improve this answer
1  
Perfect answer. By the way, I took the liberty of correcting "positive definite" to "positive semidefinite" as $\alpha_i + \lvert\alpha_i\rvert$ can be zero. –  Rahul Jan 25 '12 at 13:08
    
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$. –  Davide Giraudo Jan 25 '12 at 13:13
    
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. –  Rahul Jan 27 '12 at 14:52

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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