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

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