How to characterize real square matrices A, such that v'Av >= 0, for all real vectors v with 1'v=0 (1 is the vector of all ones)? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-25T16:11:51Z http://mathoverflow.net/feeds/question/44777 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/44777/how-to-characterize-real-square-matrices-a-such-that-vav-0-for-all-real-vec How to characterize real square matrices A, such that v'Av >= 0, for all real vectors v with 1'v=0 (1 is the vector of all ones)? daizhuo 2010-11-04T03:21:47Z 2013-01-01T22:19:30Z <p>I derive this question while trying to prove the monotonicity of a differentiable vector function $f(x)$ that maps from $X\subset R^n$ to $R^n$ (Here function $f(x)$ is called monotone if $(x-y)'(f(x)-f(y))\geq 0$, $\forall x,y\in X$). The domain $X$ only consists of vectors $x$ such that $1'x=0$, here $1$ is the vector of all ones.</p> <p>Using the mean-value theorem, we have that $f(x)$ is locally monotone at $x$ (namely $(y-x)'(f(y)-f(x))\geq 0$, $\forall y\in X$) if its Jacobian matrix evaluated at $x$, which we label as $A$, satisfies the following condition:</p> <p>$$v'Av\geq 0,\quad \forall v \text{ such that } 1'v=0.$$</p> <p>This is a weaker condition than positive semidefiniteness. However, while there are a number of ways to characterize positive semidefinite matrices, for example, see <a href="http://en.wikipedia.org/wiki/Positive-semidefinite_matrix#Characterizations" rel="nofollow">this Wikipedia page</a>, how can I characterize the above defined matrices?</p> http://mathoverflow.net/questions/44777/how-to-characterize-real-square-matrices-a-such-that-vav-0-for-all-real-vec/44780#44780 Answer by Gerry Myerson for How to characterize real square matrices A, such that v'Av >= 0, for all real vectors v with 1'v=0 (1 is the vector of all ones)? Gerry Myerson 2010-11-04T03:52:09Z 2010-11-04T03:52:09Z <p>I don't know. For $n=2$, it comes down to $\pmatrix{a&amp;b\cr c&amp;d\cr}$ such that $a+d\ge b+c$, a condition I don't recall having seen before. </p> http://mathoverflow.net/questions/44777/how-to-characterize-real-square-matrices-a-such-that-vav-0-for-all-real-vec/44789#44789 Answer by S. Sra for How to characterize real square matrices A, such that v'Av >= 0, for all real vectors v with 1'v=0 (1 is the vector of all ones)? S. Sra 2010-11-04T08:28:57Z 2013-01-01T22:19:30Z <p>If $A$ is symmetric, then the matrices that you mention are called:</p> <p><strong>Conditionally positive definite</strong> (CPD) --- these are intimately related to the venerable <em>infinitely divisible matrices</em></p> <p>There is a vast amount of literature on these matrices, some useful pointers can already be found in R. Bhatia's wonderful book: <em>Positive definite matrices</em></p> <p>There are some basic algorithmic approaches to check whether a matrix is CPD or not (e.g., Ref. 3 below)</p> <p>A simple characterization is given by the following. Let $A$ be an $n \times n$ Hermitian matrix, and let $B$ be the $(n-1) \times (n-1)$ matrix with entries</p> <p>$$b_{ij} = a_{ij} + a_{i+1,j+1} - a_{i,j+1} - a_{i+1,j}$$</p> <p>Then $A$ is CPD <em>if and only if</em> $B$ is positive-definite.</p> <p><strong>References</strong></p> <ol> <li>R. Bhatia. <em>Positive definite matrices</em> (Chapter 5)</li> <li>R. B. Bapat and T. E. S. Raghavan. Nonnegative matrices and applications (Chapter 4)</li> <li>Kh. D. Ikramov and N. V. Savel'eva. <em>Conditionally positive definite matrices</em>, J. Mathematical Sciences, Vo. 98, No. 1, 2000.</li> <li>R. A. Horn. The theory of infinitely divisible matrices and kernels (e.g. here : <a href="http://www.ams.org/journals/tran/1969-136-00/S0002-9947-1969-0264736-5/S0002-9947-1969-0264736-5.pdf" rel="nofollow">http://www.ams.org/journals/tran/1969-136-00/S0002-9947-1969-0264736-5/S0002-9947-1969-0264736-5.pdf</a>)</li> </ol> http://mathoverflow.net/questions/44777/how-to-characterize-real-square-matrices-a-such-that-vav-0-for-all-real-vec/44851#44851 Answer by Will Jagy for How to characterize real square matrices A, such that v'Av >= 0, for all real vectors v with 1'v=0 (1 is the vector of all ones)? Will Jagy 2010-11-04T17:53:01Z 2010-11-04T17:53:01Z <p>I don't think anyone knows what you mean by monotonicity of a vector-valued function, or why you are mixing together linear transformations and quadratic forms. In particular your matrix $A$ has the property you describe if and only if $(A + A^T) / 2$ has the property. Take any square matrix $B,$ take its skew-symmetric part $C = (B - B^T)/2,$ then for any column vector $w$ we have $w^T C w = 0.$ Put another way, your condition is far more sensible for the (symmetric) Hessian matrix of second partials for a function taking $\mathbf R^n$ to $\mathbf R.$ </p> <p>Define a matrix $Q_n$ with orthogonal columns given by this pattern (example for $n=6$): $$Q_n \; \; = \; \; \left( \begin{array}{cccccc} 1 &amp; -1 &amp; -1 &amp; -1 &amp; -1 &amp; -1\\ 1 &amp; 1 &amp; -1 &amp; -1 &amp; -1 &amp; -1 \\ 1 &amp; 0 &amp; 2 &amp; -1 &amp; -1 &amp; -1 \\ 1 &amp; 0 &amp; 0 &amp; 3 &amp; -1 &amp; -1 \\ 1 &amp; 0 &amp; 0 &amp; 0 &amp; 4 &amp; -1 \\ 1 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 5<br> \end{array} \right) .$$ Note that, if desired, $Q_n$ can be made into a genuine orthogonal matrix by dividing the column entries by $\sqrt n, \; \sqrt 2, \; \sqrt 6, \; \sqrt {12}, \; \sqrt {20}, \; \sqrt {30}$ and generally dividing column $j$ by $\sqrt {j^2 - j}$ when $j \geq 2.$</p> <p>The correct change of basis for a linear transformation matrix $E$ is $P^{-1} E P.$ The correct change of basis for a quadratic form symmetric (Gram) matrix $G$ is $U^T G U.$ The overlap of the two concepts is when we insist on an orthogonal matrix $W^T = W^{-1}$ and take $W^T G W.$</p> <p>Anyway, take $$A_S = (A + A^T) / 2.$$ Then look at $$Q_n^T A_S Q_n,$$ ignore row 1 and column 1, and check the lower right $n-1$ by $n-1$ block for positive semidefiniteness. This is exactly the condition you have asked about, but I have built in a little flexibility.</p> <p>The lower right $n-1$ by $n-1$ block is exactly $$R_n^T A_S R_n,$$ with the rectangular matrix: $$R_n \; \; = \; \; \left( \begin{array}{ccccc} -1 &amp; -1 &amp; -1 &amp; -1 &amp; -1\\ 1 &amp; -1 &amp; -1 &amp; -1 &amp; -1 \\ 0 &amp; 2 &amp; -1 &amp; -1 &amp; -1 \\ 0 &amp; 0 &amp; 3 &amp; -1 &amp; -1 \\ 0 &amp; 0 &amp; 0 &amp; 4 &amp; -1 \\ 0 &amp; 0 &amp; 0 &amp; 0 &amp; 5<br> \end{array} \right) .$$</p> <p>Finally, Suvrit gave the same answer but with rectangular matrix $S_n$ given by: $$S_n \; \; = \; \; \left( \begin{array}{ccccc} 1 &amp; 0 &amp; 0 &amp; 0 &amp; 0\\ -1 &amp; 1 &amp; 0 &amp; 0 &amp; 0 \\ 0 &amp; -1 &amp; 1 &amp; 0 &amp; 0 \\ 0 &amp; 0 &amp; -1 &amp; 1 &amp; 0 \\ 0 &amp; 0 &amp; 0 &amp; -1 &amp; 1 \\ 0 &amp; 0 &amp; 0 &amp; 0 &amp; -1<br> \end{array} \right) .$$ Look at the entries of $S_n^T A_S S_n.$ </p>