# Farkas lemma and matrix spectrum

I am currently looking at a problem of the following type :

I have a matrix $$\mathbf{M}\in\mathbb{R}^{N \times N}$$ such that it's general term is given by

$$(\mathbf{M})_{ij}=z_i \delta_{ij} - A_{ij}$$

with $$\delta_{ij}$$ the Kronecker delta, $$z_i>0$$ and $$A_{ij}>0$$ is zero on the diagonal and has some unknown structure off the diagonal (may be sparse, for example).

In my particular case, the $$A_{ij}$$ may be a full matrix with Gaussian terms of variance $$O(1/N)$$ or a sparse matrix with terms of order $$1$$.

Given a vector $$\mathbb{R}^N\ni\vec{V}>\vec{0}$$, I am trying to solve:

Find $$\vec{X}>\vec{0}$$ s.t. $$\mathbf{M}\vec{X} = \vec{V}$$.

I am aware that this type of problems may be solved using Farkas' lemma. However, I've noticed empirically that the matrices that allow this problem to have a solution all have positive spectra (for symmetric matrices), or the real part of their spectrum is positive (for general matrices). In fact if I generate a matrix with a spectrum that barely touches 0 then $$\mathbf{M}^{-1}\vec{V}$$ has positive components. If I slightly perturb the matrix just enough to have an eigenvalue become negative, then some terms of $$\mathbf{M}^{-1}\vec{V}$$ are negative.

Is there any way to make the link between Farkas'lemma and the matrix' spectrum ?

• Are you asking if the product of a positive definite matrix and vector with strictly positive components produces a vector with strictly positive components? – David M. Dec 7 '18 at 2:27