4
$\begingroup$

Suppose we have an $n \times m$ nonnegative matrix $A$, where each row sums to $1$. I wonder whether there exists an $m \times n$ nonnegative matrix $X$ that satisfies the following constraints:

  • each row of $X$ sums to $1$.
  • the diagonal entries of matrix $AX$ are all equal and they are larger or equal to any other entries of the matrix.

If the solution does not always exist, would be interesting to know necessary and sufficient conditions for such a solution to exist.

There are existence and uniqueness results for linear equations here and there, but this problem is about existence of a matrix with some particular constraints. Has been a while and still have no clue how to attack it.

Improve this question
$\endgroup$
5
  • $\begingroup$ The entries are real numbers? $\endgroup$
    – joro
    Commented Apr 18, 2016 at 11:01
  • $\begingroup$ Not necessarily, but can be taken as an additional assumption if anything interesting could come out from there. Thanks~ $\endgroup$
    – Ann
    Commented Apr 18, 2016 at 11:06
  • $\begingroup$ By "nonnegative matrix" do you mean this: en.wikipedia.org/wiki/Nonnegative_matrix $\endgroup$
    – joro
    Commented Apr 18, 2016 at 11:09
  • $\begingroup$ Yes. I mean all entries are nonnegative. $\endgroup$
    – Ann
    Commented Apr 18, 2016 at 12:18
  • $\begingroup$ I think the the matrix $X_{ij} = \frac 1 n$ does everything you want, so maybe you want another condition $\endgroup$
    – user83457
    Commented Jul 1, 2016 at 8:22

1 Answer 1

Reset to default
1
$\begingroup$

The question can be cast as the following feasibility problem (linear program): \begin{equation*} X \ge 0,\quad (AX)_{ii}=y,\ 1\le i \le n,\quad Xe=e,\quad (AX)_{ij} \le y,\ \forall i,j. \end{equation*} This is a linear program with $nm+1$ variables, and $(2n+1)m$ constraints. For a given $A$ whether the feasible set is empty of not can be determined by using a linear programming solver (see also this MO post).

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .