Cómo demostrar la ecuación $x^TAy=v$ ¿tiene solución?

Question

Problema:

Dada una matriz $A$ con forma $n\times n$ y un valor escalar $v$ consideremos el sistema de ecuaciones $$x^TAy = v,\\ \mathbf{1}_n^Tx=1, x\geq \mathbf{0}\\ \mathbf{1}_n^Ty=1, y\geq \mathbf{0}$$ donde $x, y$ están en un $n-1$ probabilidad simplex.

Consideremos el caso más sencillo

Dada una matriz $A=\begin{bmatrix} a_{1} & a_{2} \\ a_{3} & a_{4} \\ \end{bmatrix}$ y $v$ las variables de decisión son $x=\begin{bmatrix}x_1\\x_2\end{bmatrix}$ , $y=\begin{bmatrix}y_1\\y_2\end{bmatrix}$ .

el problema puede escribirse como $$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}$$

Algunos de mis intentos

De hecho se lo he puesto a Gurobi directamente sin reformulación alguna, y el solucionador siempre da una solución correcta, así que creo que se puede demostrar la existencia de una solución.

¿Cómo se llama ese problema? y ¿qué método puede resolverlo? ¿Alguna idea para demostrar que siempre existe al menos un par de $(x, y)$ satisfacen el sistema de ecuaciones anterior?

Answer 1

Las desigualdades $$ \begin{array}{rl} \mathbf{1}_n^Tx =1, &x\geq \mathbf{0}\\ \mathbf{1}_n^Ty =1, &y\geq \mathbf{0} \end{array} $$ implica $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. $$ Estas desigualdades permiten demostrar fácilmente que $$ \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} $$ Entonces la ecuación $$ x^{T}Ay=\sum_{i=1}\sum_{j=1}x_{i}\cdot A_{ij}\cdot y_{j}=v $$ tiene solución si, sólo si, $\min_{ij}A_{ij}\leq v \leq \max_{ij}A_{ij}$ . De hecho, supongamos $A_{\alpha,\beta}=\min_{ij}A_{ij}$ y $A_{\mu,\nu}=\max_{ij}A_{ij}$ configure $y_{\beta}=t$ , $y_{\nu}=1-t$ , $x_{\alpha}=t$ y $x_{\mu}=1-t$ para $0\leq t\leq 1$ . Entonces $$ 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}. $$ Ahora basta con observar que la ecuación cuadrática $$ t^{2}\cdot A_{\alpha \beta}+(1-t)^{2}\cdot A_{\mu \nu}=v $$ tiene solución en el $[0,1]$ intervalo cuando $A_{\alpha \beta}\leq v\leq A_{\mu \nu}$ .