# Maximizing the number of zero entries in a matrix

I have a matrix with a bunch of parameters in its entries, they all come in different combinations in different places of the matrix. I can post the matrix itself if requested, but I think what I mean should be pretty clear.

Now the idea is the following: how can I tell Mathematica to choose the combination of these parameters that maximizes the number of zero entries in the matrix? The only condition I have is that none of the parameters can be zero.

EDIT: Here's the matrix. The letters are my parameters, there's sixteen of them from a to p. The capital delta is a free parameter that doesn't enter the maximization process. You can set it to, say, 2 if you want.

{{b, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, {0,
d + e + n, -d + f, 0,
d + f - n, 0, 0,
0, -d + f, 0, 0, 0, 0, 0, 0,
0}, {0, -d + f,
d + f + l,
0, -d + f, 0, 0, 0,
d + f - l, 0, 0, 0, 0, 0,
0, 0}, {0, 0, 0,
j + k + m + o + p, 0,
1/2 (-Δ - Sqrt[8 + Δ^2]) o + 1/2 (-Δ + Sqrt[
8 + Δ^2]) p, -m +
o + p, 0,
0, -k + o + p,
1/2 (-Δ - Sqrt[8 + Δ^2]) o +
1/2 (-Δ + Sqrt[8 + Δ^2]) p, 0, -j + o + p,
0, 0, 0}, {0,
d + f - n, -d + f, 0,
d + f + n, 0, 0,
0, -d + f, 0, 0, 0, 0, 0, 0, 0}, {0, 0,
0, 1/2 (-Δ - Sqrt[8 + Δ^2]) o + 1/
2 (-Δ + Sqrt[8 + Δ^2]) p, 0, g +
1/4 (-Δ - Sqrt[8 + Δ^2])^2 o + 1/
4 (-Δ + Sqrt[8 + Δ^2])^2 p, 1/2 (-Δ - Sqrt[
8 + Δ^2]) o +
1/2 (-Δ + Sqrt[8 + Δ^2]) p, 0, 0,
1/2 (-Δ - Sqrt[8 + Δ^2]) o +
1/2 (-Δ + Sqrt[8 + Δ^2]) p, -g +
1/4 (-Δ - Sqrt[8 + Δ^2])^2 o + 1/
4 (-Δ + Sqrt[8 + Δ^2])^2 p, 0, 1/
2 (-Δ - Sqrt[8 + Δ^2]) o + 1/2 (-Δ + Sqrt[
8 + Δ^2]) p, 0, 0, 0}, {0, 0,
0, -m + o + p, 0,
1/2 (-Δ - Sqrt[8 + Δ^2]) o + 1/2 (-Δ + Sqrt[
8 + Δ^2]) p,
m + o + p, 0, 0,
o + p,
1/2 (-Δ - Sqrt[8 + Δ^2]) o + 1/2 (-Δ + Sqrt[
8 + Δ^2]) p, 0,
o + p, 0, 0, 0}, {0, 0, 0, 0, 0, 0, 0,
c + e + i, 0, 0,
0, -c + e, 0,
c + e - i, -c + e,
0}, {0, -d + f,
d + f - l,
0, -d + f, 0, 0, 0,
d + f + l, 0, 0, 0, 0, 0,
0, 0}, {0, 0,
0, -k + o + p, 0,
1/2 (-Δ - Sqrt[8 + Δ^2]) o + 1/2 (-Δ + Sqrt[
8 + Δ^2]) p,
o + p, 0, 0,
k + o + p,
1/2 (-Δ - Sqrt[8 + Δ^2]) o + 1/2 (-Δ + Sqrt[
8 + Δ^2]) p, 0,
o + p, 0, 0, 0}, {0, 0, 0,
1/2 (-Δ - Sqrt[8 + Δ^2]) o + 1/2 (-Δ + Sqrt[
8 + Δ^2]) p,
0, -g +
1/4 (-Δ - Sqrt[8 + Δ^2])^2 o + 1/
4 (-Δ + Sqrt[8 + Δ^2])^2 p, 1/2 (-Δ - Sqrt[
8 + Δ^2]) o +
1/2 (-Δ + Sqrt[8 + Δ^2]) p, 0, 0,
1/2 (-Δ - Sqrt[8 + Δ^2]) o + 1/2 (-Δ + Sqrt[
8 + Δ^2]) p,
g +
1/4 (-Δ - Sqrt[8 + Δ^2])^2 o + 1/
4 (-Δ + Sqrt[8 + Δ^2])^2 p, 0, 1/
2 (-Δ - Sqrt[8 + Δ^2]) o + 1/2 (-Δ + Sqrt[
8 + Δ^2])p, 0, 0, 0}, {0, 0, 0, 0,
0, 0, 0, -c + e, 0, 0, 0,
c + e + h,
0, -c + e,
c + e - h, 0}, {0, 0,
0, -j + o + p, 0,
1/2 (-Δ - Sqrt[8 + Δ^2]) o + 1/2 (-Δ + Sqrt[
8 + Δ^2]) p,
o + p, 0, 0,
o + p,
1/2 (-Δ - Sqrt[8 + Δ^2]) o + 1/2 (-Δ + Sqrt[
8 + Δ^2]) p, 0,
j + o + p, 0, 0,
0}, {0, 0, 0, 0, 0, 0, 0,
c + e - i, 0, 0,
0, -c + e, 0,
c + e + i, -c + e, 0}, {0, 0, 0, 0, 0, 0,
0, -c + e, 0, 0, 0,
c + e - h,
0, -c + e,
c + e + h, 0}, {0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, a}}

• Ok I'll try. Anyway, by staring at the matrix I imposed some conditions BY HAND that gave me what I think is the good result, but since I have to extend this procedure to matrices with an arbitrary number of parameters I would like to know if there's an "algorithmic" way of doing this. Feb 2 '15 at 11:02
• I think linear algebra is not needed here, since by calling list = Tally@Flatten[FullSimplify[mat]] where mat is your matrix, you can see how many times each term shows up. At that point, you could theoretically solve for when each term is zero, and see which one gives the best result or something. But I'm not quite sure what the best way to do that is, though... so this might be tough. Feb 2 '15 at 15:25
• @DumpsterDoofus Thanks for the input, I'll see what I can do. The problem is that when you solve for a particular equation you impose conditions on the other ones, and I would like to have a way of maximizing the number of solutions that give me zero. In this case I can do it by hand, but say you have a 1000x1000 matrix with 1000 parameters. Then you need an algorithm or something! Feb 2 '15 at 16:17
• Yeah, I'm not really sure how to do this. If you don't get an answer here within a day or two, you might try posting your question at SciComp Beta. Feb 2 '15 at 16:33
• For the matrix in your post, with Δ = 2, how many entries did you manage to make 0 by hand? I called your matrix mat and made a list of variables vars = {a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p} and did Maximize[{Count[Flatten[mat /. Δ -> 2], 0], And @@ ((# != 0) & /@ vars)}, vars] which gave me {186, {a -> -1, b -> -1, c -> -1, d -> -1, e -> -1, f -> -1, g -> -1, h -> -1, i -> -1, j -> -1, k -> -1, l -> -1, m -> -1, n -> -1, o -> -1, p -> -1}}. Feb 4 '15 at 11:03

Ok, I'm not sure if I'm breaking any protocol by answering my own question but it wouldn't fit in the comments.

I tried to work on the answers you guys gave in the comments. So I came up with the argument that DumpsterDoofus gave, creating a list that gives me the number of times that some specific combination of the coefficients shows up.

list = Tally@Flatten[FullSimplify[mat]]

The idea is then to solve for the equation that shows up the most number of times, then put this solution back in the list and solve for the next one that shows up the most and so on. I did this with a For loop.

listvar = Sort[Tally@Flatten[FullSimplify[mat]], #1[[2]] > #2[[2]] &];

For[w = 2, w <= Length[listvar], w++, {Flatten[Solve[listvar[[w, 1]] == 0, vars]]; listvar = Simplify[ Sort[listvar /. Flatten[Solve[listvar[[w, 1]] == 0, vars]], #1[[2]] > #2[[2]] &]];}]

What I get is the following

In[205]:= listvar

Out[205]= {{0, 186}, {0, 16}, {0, 8}, {0, 8}, {0, 6}, {0, 2}, {4 d, 2}, {0, 2}, {0, 2}, {0, 2}, {0, 2}, {0, 2}, {0, 2}, {0, 2}, {4 c, 2}, {0, 2}, {4 c, 2}, {0, 1}, {c + 3 d, 1}, {0, 1}, {4 d, 1}, {0, 1}, {0, 1}, {0, 1}, {a, 1}}

Which clearly has one problem: some of the variables have been set to zero! The problem here is that I don't know how to tell him that the variables vars CANNOT be zero! Otherwise I would have pretty much solved it, I think. Any help?

• "I'm not sure if I'm breaking any protocol by answering my own question but it wouldn't fit in the comments." -- Not a problem! Self-answers are encouraged. Feb 8 '15 at 12:13