I'm trying to think through a network flow problem, and while I could probably shuffle this into a form that a linear programming method would work, it feels like there ought to be something more elegant...
Suppose I have $m$ linear inequalities
$$A x \leq b$$
Where $x$ is of length $n$ and $b$ is of length $m$, and both are known. $A$, then, is an $m \times n$ matrix of unknown coefficients, but subject to the constraint that each column of coefficients must sum to one (i.e. a percentage of the flow being divided). I don't need to know a particular solution per se, I'm more concerned with knowing does such a solution exist. It's been a while since I took Linear Algebra so apologies if I'm overlooking something obvious, but is there a reasonably general way of figuring this out?
We have $A x \leq b$, where $A \in \mathbb R^{m \times n}$ is unknown and $x \in \mathbb R^n$ and $b \in \mathbb R^m$ are given. Vectorizing,
$$(x^T \otimes I_m) \, \mbox{vec} (A) \leq b$$
We also have the equality constraints $1_m^T A = 1_n^T$. Vectorizing again,
$$(I_n \otimes 1_m^T) \, \mbox{vec} (A) = 1_n$$
Thus, we have $m n$ unknowns, $m$ linear inequality constraints and $n$ linear equality constraints. Pick an arbitrary linear objective function and use linear programming to determine whether the polytope defined by the linear constraints is empty or not.