# Checking powers of a matrix for zeros

I'm currently working on a project that deals with numerical semigroups and their connection to matrices. I'm pretty new to Mathematica, so I wouldn't be surprised if my question has a simple solution; nevertheless I can't find it haha!

I need code that will check the entries in a matrix to see if any of them are zero, and if there is at least one zero in the matrix, take the next power of the matrix and check it again until all of the entries are non-zero. All of the matrices I am working with WILL become completely non-zero, so I don't need to worry about an infinite loop or anything. I was thinking that I could just multiply all of the elements in the given matrix and if the product = 0, then loop back through. Either that or scan elements of the matrix individually since the matrices aren't any bigger than 5 x 5.

Any help is greatly appreciated!

P.S, -- If anyone has a method of then checking individual elements of a matrix to see if they are nonzero, and if they are, then adding the current power of that matrix to a set of numbers, I would be grateful to hear how it could be done. This is secondary to the above question though.

## 2 Answers

mattest={{1, 1, 1, 1, 0}, {0, 1, 1, 0, 0}, {1, 1, 0, 1, 0},
{0, 1, 0, 1, 1}, {0, 1, 0, 1, 0}}

pow = 1
While[Min@Unitize@(cur = MatrixPower[mattest, pow]) == 0, pow++]
{pow, cur}

(*

{3, {{4, 12, 6, 8, 3}, {2, 5, 3, 3, 1}, {3, 9, 4, 6, 2},
{1, 7, 3, 4, 2}, {1, 5, 2, 3, 1}}}

*)


This returns a list with the power at stop, and the resulting matrix.

If you don't care about the power needed, but just the end result,

NestWhile[Dot[mattest, #] &, mattest, Min@Unitize@# == 0 &]


will just give the ending matrix. Replace NestWhile with NestWhileList to get a list of the progressions of powers, where the length of the result list corresponds to the power needed to reach the goal.

I've assumed numeric matrix, if symbolic, please clarify. Second part of question is unclear to me, perhaps clarify?

Update: For part two of your query:

mattest={{1, 1, 1, 1, 0}, {0, 1, 1, 0, 0}, {1, 1, 0, 1, 0},
{0, 1, 0, 1, 1}, {0, 1, 0, -1, 0}}

Module[{lst = #, ele = #2, nl},
nl = NestWhileList[Dot[lst, #] &, lst, Min@Unitize@# == 0 &][[All, Sequence @@ ele]];
Pick[Range@Length@nl, nl, 0]] &[mattest, {5, 3}]

(*
{1, 3, 4}
*)


Stops when array has no zero entries.

The arguments are the target matrix and the position of the desired element to follow ({5,3} in this example). This can be chopped down probably for efficiency, but not likely an issue with your stated problem sizes.

• The second part pertains to a specific entry in the matrix, so row 1 column 1. Say I square the matrix, and the entry in 1,1 is nonzero, then I want to add 2 (the power) to the "list" of powers which produce a non-zero number in the 1,1 spot... Does that make sense? Thanks for your help by the way! – Dan May 21 '14 at 23:12
• @Dan: See update. – ciao May 21 '14 at 23:34
• Thanks so much again!!! At the expense of sounding like a total newbie, do I need to put this code in to a workbook or something different to make it work? My advisor mentioned something called 'Workbench' to put my code in to but I have no clue what that is...? – Dan May 21 '14 at 23:36
• @Dan: Well, you need to be in some kind of Mathematica session obviously. Workbench is just an add-on product that has fancier IDE features, not needed to run things - just cut-n-paste the code into a notebook... – ciao May 21 '14 at 23:38
fp1 = Function[{m}, FixedPoint[If[!FreeQ[#, 0], Dot[m, #], #] &, m]];
fp2 = Function[{m}, FixedPoint[If[Min@# == 0, Dot[m, #], #] &, m]];
fp3 = Function[{m}, FixedPoint[If[Min@Unitize@# == 0, Dot[m, #], #] &, m]];

mtrx = {{1, 1, 1, 1, 0}, {0, 1, 1, 0, 0}, {1, 1, 0, 1, 0},
{0, 1, 0, 1, 1}, {0, 1, 0, 1, 0}}
fp1@mtrx
fp1@mtrx ==fp2@mtrx == fp3@mtrx
(* {{4, 12, 6, 8, 3}, {2, 5, 3, 3, 1}, {3, 9, 4, 6, 2},
{1, 7, 3, 4,  2}, {1, 5, 2, 3, 1}}
True *)


Unlike fp1 and fp3, fp2 works only for lists with non-negative entries. For lists with non-negative entries fp2 is faster than both fp1 and fp3.

Update: Although the OP's case of interest involves small matrices, it may be of interest to consider the timings for larger matrices.

With rasher's two functions

fp4 = (pow = 1; While[Min@Unitize@(cur = MatrixPower[#, pow]) == 0, pow++]; cur) &
fp5 = Function[{m}, NestWhile[Dot[m, #] &, m, Min@Unitize@# == 0 &]]


and a random matrix

tstMat = RandomChoice[{0, 1}, {1000, 1000}];


I get the following timings:

r1 = fp1@tstMat; // Timing (* {0.125000, Null} *)
r2 = fp2@tstMat; // Timing (* {0.062500, Null} *)
r3 = fp3@tstMat; // Timing (* {0.265625, Null} *)
r4 = fp4@tstMat; // Timing (* {0.796875, Null} *)
r5 = fp5@tstMat; // Timing (* {0.250000, Null} *)
r1 == r2 == r3 == r4 == r5
(* True *)


Update 2: To return the power at which all matrix entries become non-zero, you can modify fp1, fp2 and fp3 as follows:

fp1b = (Function[{m}, Block[{i = 1},
{FixedPoint[If[! FreeQ[#, 0], i++; Dot[m, #], #] &,  m], i}]])

fp1b@mtrx
(* {{{4, 12, 6, 8, 3}, {2, 5, 3, 3, 1}, {3, 9, 4, 6, 2}, {1, 7, 3, 4, 2},
{1, 5, 2, 3, 1}}, 3} *)

• +1 for FixedPoint use. Note however fp2 fails if negative entries are present. – ciao May 21 '14 at 23:01
• IIs there a way to make this method return the power that the code stopped at? – Dan May 21 '14 at 23:29
• @rasher, yes... that indeed was the reason for fp1 - not realizing at the time the reason behind your use of Min@Unitize:) Updated with a note on this. – kglr May 21 '14 at 23:36
• @Dan, please see the update for returning the power at which the fixed point is reached. – kglr May 22 '14 at 21:33