Assume we have the under-determined linear system $$ Ax = y $$ $$A \in \mathbb R^{m \times n}_{\geq 0},\, y \in \mathbb R^m_{\geq 0},\, m < n,$$ for which we know a non-negative solution $x^* \in \mathbb R^n_{\geq 0}$. The problem is to verify that $x^*$ is the unique non-negative solution.

**Note.** I use $\mathbb R_{\geq 0}$ as a notation for a set of non-negative real numbers. Note that all the parameters of the problem are non-negative.

I know the following (hopefully correct) deterministic algorithm to solve the problem:

- Let $I = \{ i | x^*_i \neq 0 \}$ is the support of a vector $x^*$.
- Let $A_I$ be a matrix consisting of columns of $A$ with indexes in $I$. If $A_I$ has rank less than number of its columns, there exists for sure another non-negative solution. (Proof omitted. Intuition: we can take some solution of $A_I e = 0$ of small enough norm, then $(x^* + e)$ is another non-negative solution of original system).
- Otherwise consider the following linear programming problem: $$ dx \rightarrow \max $$ $$ \text{s.t. } Ax = y, x \geq 0 $$ where $d = (d_i) \in \mathbb R^n$ is defined as follows: $$ d_i = \begin{cases} 1, \text{ if } x^*_i = 0, \\ 0, \text{ otherwise}. \end{cases} $$
- The original system has unique non-negative solution if and only if the aforementioned linear programming problem outputs $x^*$ as its solution. (Intuition: if solving LPP gives us the same $x^*$, then all the non-negative solutions of $Ax=y$ have zeros at positions $\{1,2,\dots,n\} \setminus I$. Then step 2 guarantees the uniqueness).

However, I want to have a more efficient algorithm as I need to verify plenty of such systems with a fixed matrix $A$ of size $n \approx 300$ for different pairs $(x^*,y)$ where $y=Ax^*$.

I did not find faster deterministic algorithm so I decided to check out randomized algorithms hoping that this can reduce complexity. Does anyone know an algorithm to solve the original problem that is

- Las Vegas? I.e. an algorithm that uses randomness but gives solution that is always correct.
- Monte Carlo? I.e. an algorithm that gives a wrong answer with small probability. I will then run it couple of times to make error probability small enough.

**P.S.** I am aware about questions here and here. However they do not explicitly speak about randomized algorithms.