4
$\begingroup$

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.

$\endgroup$

1 Answer 1

5
$\begingroup$

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.

$\endgroup$
6
  • $\begingroup$ 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$? $\endgroup$
    – Ypbor
    Aug 12 at 13:32
  • $\begingroup$ 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. $\endgroup$ Aug 12 at 13:41
  • $\begingroup$ 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. $\endgroup$
    – Ypbor
    Aug 12 at 13:49
  • 1
    $\begingroup$ 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". $\endgroup$ Aug 12 at 13:52
  • $\begingroup$ 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.) $\endgroup$
    – Ypbor
    Aug 24 at 15:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.