# How to prove the equation $x^TAy=v$ has a solution?

Problem:

Given a matrix $$A$$ with shape $$n\times n$$ and a scalar value $$v$$, consider the equation system $$x^TAy = v,\\ \mathbf{1}_n^Tx=1, x\geq \mathbf{0}\\ \mathbf{1}_n^Ty=1, y\geq \mathbf{0}$$ where $$x, y$$ are in a $$n-1$$ probability simplex.

Consider a simplest case

Given a matrix $$A=\begin{bmatrix} a_{1} & a_{2} \\ a_{3} & a_{4} \\ \end{bmatrix}$$ and $$v$$, the decision variable are $$x=\begin{bmatrix}x_1\\x_2\end{bmatrix}$$, $$y=\begin{bmatrix}y_1\\y_2\end{bmatrix}$$.

the problem can be written as $$a_1x_1y_1+a_2x_1y_2+a_3x_2y_1+a_4x_2y_2=v\\ x_1+x_2=1, x\geq \mathbf{0}\\ y_1+y_2=1, y\geq \mathbf{0}$$

Some of my tries

I actually put it to Gurobi directly without any reformulation, and the solver always gives a correct solution, so I think the existence of a solution can be proved.

What is such a problem called? and what method can solve it? Any idea to prove that there always exists at least one pair of $$(x, y)$$ satisfy the above equation system?

• Hello :) There is not always a solution. Consider $M:=\{(x,y)\in\mathbb{R}_{\geq 0}^{2\times2}\mid x_1+x_2=y_1+y_2=1\}$. It is compact set. Hence $x^TAy$ has a minimum and a maximum for $(x,y)\in M$. Commented Sep 19, 2021 at 13:36
• @Jochen, thank you for your comment. I see the solution not always exists now. Any idea of if $A$ holds some kind of properties (symmetric, definite, etc.) or under what situation, then it will have a solution? Commented Sep 19, 2021 at 13:56
• For any $A$ there is a $v$, such that there are no $x, y\in\operatorname{conv}(e_1, \ldots, e_n)$ with $x^TAy=v$. Observe $|x^TAy|\leq \|x\|\cdot\|A\|\cdot\|y\|\leq \|A\|$. Hence for any $v>\|A\|$, there is no solution. Here $\|\cdot\|$ is the euclidean norm or the operatornorm wrt the euclidean norm. Commented Sep 19, 2021 at 14:38
• Both of them should be in bold, I have just made an edit. Sorry for the mistakes in details. Commented Sep 19, 2021 at 18:10

The inequalities $$\begin{array}{rl} \mathbf{1}_n^Tx =1, &x\geq \mathbf{0}\\ \mathbf{1}_n^Ty =1, &y\geq \mathbf{0} \end{array}$$ implies $$0\leq x_{i}\leq 1$$, $$0\leq y_{j}\leq 1$$, $$x_{1}+\ldots+x_{n}=1 \quad \mbox{ and } \quad y_{1}+\ldots+y_{n}=1.$$ These inequalities make it easy to proof that $$\min_{ij}A_{ij}\leq x^{T}Ay=\sum_{i=1}\sum_{j=1}x_{i}\cdot A_{ij}\cdot y_{j}\leq \max_{ij}A_{ij}$$ Then the equation $$x^{T}Ay=\sum_{i=1}\sum_{j=1}x_{i}\cdot A_{ij}\cdot y_{j}=v$$ has solution if, only if, $$\min_{ij}A_{ij}\leq v \leq \max_{ij}A_{ij}$$. In fact, supose $$A_{\alpha,\beta}=\min_{ij}A_{ij}$$ and $$A_{\mu,\nu}=\max_{ij}A_{ij}$$ set $$y_{\beta}=t$$, $$y_{\nu}=1-t$$, $$x_{\alpha}=t$$ and $$x_{\mu}=1-t$$ for $$0\leq t\leq 1$$. Then $$x^{T}Ay = t\cdot A_{\alpha \beta}\cdot t+(1-t)\cdot A_{\mu \nu}\cdot (1-t) = t^{2}\cdot A_{\alpha \beta}+(1-t)^{2}\cdot A_{\mu \nu}.$$ Now just note that the quadratic equation $$t^{2}\cdot A_{\alpha \beta}+(1-t)^{2}\cdot A_{\mu \nu}=v$$ has solution in the $$[0,1]$$ interval when $$A_{\alpha \beta}\leq v\leq A_{\mu \nu}$$.