5
$\begingroup$

Is there a simple way to test in Mathematica whether a non-negative square matrix $A$ is primitive?

Primitive means that for some positive integer power $k$, all entries of $A^k$ (matrix power) are positive.

$\endgroup$
  • $\begingroup$ Have you seen this? $\endgroup$ – J. M. is away Jul 26 '17 at 5:28
  • $\begingroup$ @J.M. Bingo! I got it, thanks. $\endgroup$ – becko Jul 26 '17 at 14:59
6
$\begingroup$
primitiveQ1 = MarkovProcessProperties[DiscreteMarkovProcess[1, #], "Primitive"] &

Alternatively,

primitiveQ2 = RandomProcesses`MarkovChainDump`PrimitiveStochasticMatrixQ

This works in both version 9 and version 11 provided DiscreteMarkovProcess is run before it is used (thanks: @ChrisK).

In case it doesn't work even after invoking DiscreteMarkovProcess first,the following is its implementation (after replacing intermediate function calls):

primitiveQ2[m_] := With[{n = Length[m]}, 
  MatchQ[SparseArray`StronglyConnectedComponents[m], {{__Integer}}] && 
 (Tr[m] > 0 || Min[MatrixPower[m, n (n - 2) + 2]] > 0)]

Examples:

mat1 = {{1/2, 1/2, 0, 0}, {1/2, 1/2, 0, 0}, {1/4, 1/4, 1/4, 1/4}, {0, 0, 0, 1}};
mat2 = {{0, 1/3, 0, 2/3, 0}, {1/2, 0, 0, 0, 1/2}, {0, 0, 1/2, 1/2, 0}, 
  {1/3, 0, 1/3, 1/3, 0}, {1/3, 1/3, 0, 0, 1/3}};

primitiveQ1 /@ {mat1, mat2}

{False, True}

primitiveQ2 /@ {mat1, mat2}

{False, True}

$\endgroup$
  • $\begingroup$ I don't have this package. Where can I find it? $\endgroup$ – becko Oct 10 '17 at 17:28
  • $\begingroup$ @becko, it comes built-in in version 9. $\endgroup$ – kglr Oct 10 '17 at 17:36
  • $\begingroup$ It's no longer there in v11.1 $\endgroup$ – becko Oct 10 '17 at 18:06
  • $\begingroup$ @becko, I added its implementation which works in version 11. $\endgroup$ – kglr Oct 10 '17 at 18:31
  • 1
    $\begingroup$ @kglr Your first version works for me in v11.2, after running DiscreteMarkovProcess first. $\endgroup$ – Chris K Oct 12 '17 at 2:59

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.