Testing if the Null Space of a Matrix Contains a Positive Vector

linear algebramatrices

Let $A$ be an $n\times m$ matrix, with $n<m$. Is there a way to test if the null space of $A$ contains a positive vector? By positive vector, I mean a vector with only non-negative entries and different from zero.

Best Answer

It suffices to find a matrix $M$ whose columns form a basis of the nullspace and solve the following linear programming problem:

\begin{align} \min_x\quad & c^TMx \\ \text{such that }\quad & -Mx \leq -\vec 1\\ &x \in \Bbb R, \end{align} where $c$ can be any $m \times 1$ vector. We make use of the following "trick" here: if an element of the nullspace with positive elements exists, then it is of course possible to scale this element so that its entries are greater than or equal to $1$. So, it suffices to consider the constraint where all entries of the vector are strictly greater than $1$.

If you merely want to assess existence, then you can take $c$ to be a zero vector as I have below, but you might prefer to choose a different $c$ as a niceness heuristic. For example, taking $c$ to be a vector of $1$'s results in a solution with minimal $1$-norm.

If the inequalities seems strange, that's because they have been arranged to accommodate the nature of the inputs to scipy's linprog function.

Here's the Python script (modified for relevancy) that I used to deal with a very similar problem.

import numpy as np
import scipy.linalg as la
from scipy.optimize import linprog

M = la.null_space(A)
n,m = M.shape
c = np.zeros(m)
        
A_ub = -M
b_ub = -np.ones(n)

res = linprog(c,A_ub = A_ub, b_ub = b_ub, bounds = (None,None))
print(res)

The print(res) command gives you a summary of the result. The True/False after success: tells you whether a satisfactory vector $x$ exists. This condition is stored as res.success. The vector $x$ is stored as res.x, and the corresponding element of the nullspace is [email protected].

Implementation of the simpler method, per the helpful comment:

import numpy as np
import scipy.linalg as la
from scipy.optimize import linprog

n,m = A.shape

b_eq = np.zeros(n)
c = np.zeros(m)

res = linprog(c,A_eq = A, b_eq = b_eq, bounds = (1,None))
print(res)

If the outcome is "success", then the feasible element of the nullspace is given by res.x.

Related Question