4

Suppose $A$ is a $m\times n$ Markov matrix, and $C$ is a $m\times k$ Markov matrix. How to decide (analytically or numerically) whether there is a $n\times k$ Markov matrix $B$ such that $AB=C$? I feel that it is a question of feasibility in linear programming.

SecretAgentMan
  • 1,895
  • 2
  • 13
  • 39
Ypbor
  • 163
  • 2

1 Answers1

5

You could solve this as a Linear Programming feasibility problem.

A Markov Matrix is also known as a stochastic matrix.

So the constraints are:

All elements of B are nonnegative.

All rows sums of B equal 1.

$AB = C$

Edit: Adding CVX program as an easy way to formulate and solve this under MATLAB, given OP comments below.

cvx_begin
variable B(n,k)
B >= 0
sum(B,2) == 1
A*B == C
cvx_end

This will either be determined to be infeasibile, or it will be solved to "optimality", in which case B will contain a feasible solution after CVX concludes.

prubin
  • 39,078
  • 3
  • 37
  • 104
Mark L. Stone
  • 13,392
  • 1
  • 31
  • 67
  • Thanks for answering. I was wondering whether this is a problem that was already investigated so that there are some analytical results about it. Or is there software that can solve this problem for given $A$ and $C$? – Ypbor Aug 12 '22 at 13:32
  • I am not aware of any analytical results or software designed for this specific problem, but can't say for sure no such thing exists. But it should be very straightforward to enter the formulation I provided in any Linear Programming solver, which will either determine it is feasible and provide a feasible B, or it will determine it is not feasible. – Mark L. Stone Aug 12 '22 at 13:41
  • Could you please recommend a Linear Programming solver? I am a greenhand. It seems that one can do linear programming in Matlab, but it has the form of minimization while I only care feasibility. – Ypbor Aug 12 '22 at 13:49
  • 1
    If you use MATLAB, you can download CVX for free and use that (any needed solver is included and installed for you). I will edit my answer to show the CVX program. Also note that all LP solvers can accept feasibility problems. You either omit the objective, if it lets you, or use the objective of "0". – Mark L. Stone Aug 12 '22 at 13:52
  • When CVX indicates "infeasible", does it only mean "numerically infeasible"? (That is, there may be feasible points but they are not found by the algorithm.) – Ypbor Aug 24 '22 at 15:47
  • The solvers (and CVX) solve or make feasibility determinations to within a numerical tolerance. All solvers called by CVX used double precision (Gurobi might use higher precision internally in some places in some cases). You can read http://cvxr.com/cvx/doc/solver.html#interpreting-the-results and http://cvxr.com/cvx/doc/support.html#handling-numerical-issues – Mark L. Stone Aug 24 '22 at 16:11