3 Fixed errors in the references...

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 (esp. Chapter 5)
2. R. B. Bapat and T. E. S. Raghavan. Nonnegative matrices and applications (Chapter 4)
3. Kh. D. Ikramov and N. V. SaveFevaSavel'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.pdfhttp://www.ams.org/journals/tran/1969-136-00/S0002-9947-1969-0264736-5/S0002-9947-1969-0264736-5.pdf)
2 added symmetry as a prereq

The

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 . Once I find the paper in my archives, I will update my answer(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 (esp. Chapter 5)
2. R. B. Bapat and T. E. S. Raghavan. Nonnegative matrices and applications (Chapter 4)
3. Kh. D. Ikramov and N. V. SaveFeva. 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
1

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. Once I find the paper in my archives, I will update my answer.

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.