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

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)?

2010-11-04T03:21:47Z

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.

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:

$$v'Av\geq 0,\quad \forall v \text{ such that } 1'v=0.$$

This is a weaker condition than positive semidefiniteness. However, while there are a number of ways to characterize positive semidefinite matrices, for example, see this Wikipedia page, how can I characterize the above defined matrices?

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)?

2010-11-04T03:52:09Z

I don't know. For $n=2$, it comes down to $\pmatrix{a&b\cr c&d\cr}$ such that $a+d\ge b+c$, a condition I don't recall having seen before.

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)?

2010-11-04T08:28:57Z

If $A$ is symmetric, then the matrices that you mention are called:

Conditionally positive definite (CPD) --- these are intimately related to the venerable infinitely divisible matrices

There is a vast amount of literature on these matrices, some useful pointers can already be found in R. Bhatia's wonderful book: Positive definite matrices

There are some basic algorithmic approaches to check whether a matrix is CPD or not (e.g., Ref. 3 below)

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

$$b_{ij} = a_{ij} + a_{i+1,j+1} - a_{i,j+1} - a_{i+1,j}$$

Then $A$ is CPD if and only if $B$ is positive-definite.

References

R. Bhatia. Positive definite matrices (Chapter 5)
R. B. Bapat and T. E. S. Raghavan. Nonnegative matrices and applications (Chapter 4)
Kh. D. Ikramov and N. V. Savel'eva. Conditionally positive definite matrices, J. Mathematical Sciences, Vo. 98, No. 1, 2000.
R. A. Horn. The theory of infinitely divisible matrices and kernels (e.g. here : http://www.ams.org/journals/tran/1969-136-00/S0002-9947-1969-0264736-5/S0002-9947-1969-0264736-5.pdf)

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)?

2010-11-04T17:53:01Z

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

Define a matrix $Q_n$ with orthogonal columns given by this pattern (example for $n=6$): $$ Q_n \; \; = \; \; \left( \begin{array}{cccccc} 1 & -1 & -1 & -1 & -1 & -1\\ 1 & 1 & -1 & -1 & -1 & -1 \\ 1 & 0 & 2 & -1 & -1 & -1 \\ 1 & 0 & 0 & 3 & -1 & -1 \\ 1 & 0 & 0 & 0 & 4 & -1 \\ 1 & 0 & 0 & 0 & 0 & 5
\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.$

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

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.

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 & -1 & -1 & -1 & -1\\ 1 & -1 & -1 & -1 & -1 \\ 0 & 2 & -1 & -1 & -1 \\ 0 & 0 & 3 & -1 & -1 \\ 0 & 0 & 0 & 4 & -1 \\ 0 & 0 & 0 & 0 & 5
\end{array} \right) . $$

Finally, Suvrit gave the same answer but with rectangular matrix $S_n$ given by: $$ S_n \; \; = \; \; \left( \begin{array}{ccccc} 1 & 0 & 0 & 0 & 0\\ -1 & 1 & 0 & 0 & 0 \\ 0 & -1 & 1 & 0 & 0 \\ 0 & 0 & -1 & 1 & 0 \\ 0 & 0 & 0 & -1 & 1 \\ 0 & 0 & 0 & 0 & -1
\end{array} \right) . $$ Look at the entries of $ S_n^T A_S S_n.$