# PrimitiveMatrixQ?

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.

primitiveQ1 = MarkovProcessProperties[DiscreteMarkovProcess[1, #], "Primitive"] &


Alternatively,

primitiveQ2 = RandomProcessesMarkovChainDumpPrimitiveStochasticMatrixQ


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[SparseArrayStronglyConnectedComponents[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}

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