I would like to find a 19x19 matrix V such that the following inequality holds:
$$V^TAV<K$$
and where all entries of V are positive and the sum of entires in a row of V are equal to 1.
Also < is taken point wise and K and A are particular matrices specified by the problem. In particular, the ijth element of A is sign(j-i) where sign(x)=|x|/x for x≠0 and 0 for x=0.
K has the following property:
The diagonal of K is all 0's and each other entry of K is either a 1 or e where 0 < e << 1. Also Kij = 1 iff Kji = e.
Although for my specific problem there are some additional properties satisfied by A and K, I am interested in more general approaches to solving problems of this form.
So far, the best idea for solving this is to use gradient descent. In particular I was considering picking a random matrix V, then computing Q as follows:
$$Q=V^TAV-K$$
Then let $$err = ∑_{i,j} max(Qij,0) $$
and then I would try to minimize err via gradient descent
Assume you are in dimension $n$. If the lines of $V$ are $(v_1' \ldots v_n')$, then: $$V'AV=(\langle v_i,Av_j \rangle)$$ If you write $v_i=\sum_k v_{ik}e_k$, you also have: $$ \langle e_k,Ae_l \rangle =1_{k<l}-1_{k>l}$$ Thus: $$ \langle u_i,Au_j \rangle =\sum_{k,l} u_{ik} u_{jl} \langle e_k,Ae_l \rangle =\sum_{k<l} u_{ik} u_{jl} - \sum_{k>l} u_{ik} u_{jl} $$
In particular, you can see that all the coefficients are smaller than $1$ in absolute value, and that the matrix is antisymmetric (so its diagonal is zero).
Finally, thanks to this formula, if you take $V=\left(\frac1n\right)$ (with all coefficients equal to $\frac1n$), you have $V'AV=0$, which is a solution to your problem.
You can also find a constant $c$ (at least close to $1/2$ for $e$ close to $0$) such that any other matrix $\tilde V$ with $|\tilde V-V|< ce$ remains a solution.