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 ?

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.