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

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?

-
I see your definition, I must agree that you have the condition correct. The matrix you want is in fact not by nature symmetric, so the quickest method is to take the symmetric part of $A$ and apply Suvrit's answer. Note that if the result is semidefinite instead of definite, you will need to check second partial derivative information for the null directions. – Will Jagy Nov 5 '10 at 3:50

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

1. R. Bhatia. Positive definite matrices (Chapter 5)
2. R. B. Bapat and T. E. S. Raghavan. Nonnegative matrices and applications (Chapter 4)
3. Kh. D. Ikramov and N. V. Savel'eva. Conditionally positive definite matrices, J. Mathematical Sciences, Vo. 98, No. 1, 2000.
4. 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)
-
The quadratic form defined by $A$ is the same as that defined by $\frac 12 (A+A^T)$, and that is symmetric. So all you said above can be generalized to the nonsymmetric case by writing $\frac12(a_{ij}+a_{ji})$ in lieu of $a_{ij}$ – Federico Poloni Nov 4 '10 at 8:45
@Federico, true; that is the (implicit) reason why I originally rapidly typed my answer, but then for some reason, suddenly thought, what if the asymmetry of $A$ is somehow important to the OP. :-) – Suvrit Nov 4 '10 at 9:00

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

-
Thanks for your comment. I added to my question the definition of vector function monotonicity. – daizhuo Nov 5 '10 at 3:34

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.

-
Gerry, the first thing is to take the symmetric part, when $A = A_1 + A_2$ with $A_1$ symmetric but $A_2$ skew symmetric, his quadratic form is not changed by taking $A_1.$ A correct but useless answer is to demand an orthogonal change of basis to a basis with first vector parallel to $(1,1,\ldots,1).$ Then he wants the block referring to the next $n-1$ vectors positive semidefinite. – Will Jagy Nov 4 '10 at 3:59