I have an algorithm which gives me a list of solutions (in matrix form, if it is of any importance) of an equation. Some of these solutions are particular cases of other. For example, in this list there can be solutions

(10a0b1−a000)\begin{pmatrix}

1 & 0 & a \\

0 & b & 1-a \\

0 & 0 & 0

\end{pmatrix} and (10a0a1−a000)\begin{pmatrix}

1 & 0 & a \\

0 & a & 1-a \\

0 & 0 & 0

\end{pmatrix}. The second one is a particular case of the first, so I would like to eliminate it. The original list is quite big, hence it would be more or less exhausting to clean it of all such cases by hand. Is there a way to do it automatically?

I know that there is the command Cases in Mathematica, but at this point I do not see a way to adapt it for that purpose.

The example above is artificial, a peace of my real list could look as something like the matrices below (it happens so that parameters are named in quite an arbitrary way, but clearly some of the solutions are particular cases of others)

(0−1−x[1][2][1]−x[1][1][1]−10−10−100−1)\begin{pmatrix}

0 && -1 && -x[1][2][1] && -x[1][1][1]\\

-1 && 0 && -1 &&0\\

-1 && 0 && 0 && -1\\ \end{pmatrix}

(0−120−10−10−11−1−1)\begin{pmatrix}

0 && -1 && 2 && 0\\

-1 && 0 && -1 && 0\\

-1 && 1 && -1 && -1\\

\end{pmatrix}

(0−1x[1][1][1]−x[1][1][1]−10−10−100−1)\begin{pmatrix}

0 && -1 && x[1][1][1] && -x[1][1][1] \\

-1 && 0 && -1 && 0 \\

-1 && 0 && 0 && -1 \\

\end{pmatrix}

(0−10−x[1][1][1]−10−10−100−1)\begin{pmatrix}

0 && -1 && 0 && -x[1][1][1] \\

-1 && 0 && -1 && 0 \\

-1 && 0 && 0 && -1 \\

\end{pmatrix}

(0−100−1−C[1]−10−1−C[2]0−1)\begin{pmatrix}

0 && -1 && 0 && 0 \\

-1 && -C[1] && -1 && 0 \\

-1 && -C[2] && 0 && -1 \\

\end{pmatrix}

(0−100−10−10−1−C[1]0−1)\begin{pmatrix}

0 && -1 && 0 && 0 \\

-1 && 0 && -1 && 0 \\

-1 && -C[1] && 0 && -1 \\

\end{pmatrix}

(0−100−1−C[1]−10−1−C[1]0−1)\begin{pmatrix}

0 && -1 && 0 && 0 \\

-1 && -C[1] && -1 && 0 \\

-1 && -C[1] && 0 && -1 \\

\end{pmatrix}

And in this case I want to delete all except for

(0−1−x[1][2][1]−x[1][1][1]−10−10−100−1)\begin{pmatrix}

0 && -1 && -x[1][2][1] && -x[1][1][1]\\

-1 && 0 && -1 &&0\\

-1 && 0 && 0 && -1\\ \end{pmatrix}

(0−120−10−10−11−1−1)\begin{pmatrix}

0 && -1 && 2 && 0\\

-1 && 0 && -1 && 0\\

-1 && 1 && -1 && -1\\

\end{pmatrix}

(0−100−1−C[1]−10−1−C[2]0−1)\begin{pmatrix}

0 && -1 && 0 && 0 \\

-1 && -C[1] && -1 && 0 \\

-1 && -C[2] && 0 && -1 \\

\end{pmatrix}

All the matrices in Mathematica format:

{{{-1, -x[1][2][1], -x[1][1][1]}, {0, -1, 0}, {0, 0, -1}}, {{0, 1, -2,

0}, {-1, 0, -1, 0}, {-1, 1, -1, -1}}, {{0, -1,

x[1][1][1], -x[1][1][1]}, {-1, 0, -1, 0}, {-1, 0, 0, -1}}, {{0, -1,

0, -x[1][1][1]}, {-1, 0, -1, 0}, {-1, 0, 0, -1}}, {{0, -1, 0,

0}, {-1, -C[1], -1, 0}, {-1, -C[2], 0, -1}}, {{0, -1, 0, 0}, {-1,

0, -1, 0}, {-1, -C[1], 0, -1}}, {{0, -1, 0, 0}, {-1, -C[1], -1,

0}, {-1, -C[1], 0, -1}}}

=================

1

You’ll have to be more specific about the conditions and constraints upon your problem and thus what constitutes a special case. For instance, do you consider a special case to include the condition that three variables have a special relationship, leading to degeneracy?

– David G. Stork

May 4 ’15 at 16:51

@DavidG.Stork Actually it is a specific of the algorithm. It returns a list of solutions, which are in parametric form. Among them some solutions depend on several parameters, some are just integral matrices, thereby depend on no parameters. In the example above I would like to remove the second case since any solution of this form can be represented as a solution of the first form. I can try to explain the situation in a more detailed way if there is a need.

– Hypsoline

May 4 ’15 at 17:11

I don’t think there’s anything built in to do it. It’s probably not too hard to implement something but you’ll need to supply a few example cases for people to test their ideas with.

– Simon Woods

May 4 ’15 at 17:13

@SimonWoods Thank you, I have added some examples to the original question.

– Hypsoline

May 4 ’15 at 17:35

show the expected result for your new example ( and post in input form of ypu can.. )

– george2079

May 4 ’15 at 17:59

=================

2 Answers

2

=================

First:

sols = {{{0, -1, -x[1][2][1], -x[1][1][1]}, {-1, 0, -1, 0}, {-1, 0, 0, -1}},

{{0, 1, -2, 0}, {-1, 0, -1, 0}, {-1, 1, -1, -1}},

{{0, -1, x[1][1][1], -x[1][1][1]}, {-1, 0, -1, 0}, {-1, 0, 0, -1}},

{{0, -1, 0, -x[1][1][1]}, {-1, 0, -1, 0}, {-1, 0, 0, -1}},

{{0, -1, 0, 0}, {-1, -C[1], -1, 0}, {-1, -C[2], 0, -1}},

{{0, -1, 0, 0}, {-1, 0, -1, 0}, {-1, -C[1], 0, -1}},

{{0, -1, 0, 0}, {-1, -C[1], -1, 0}, {-1, -C[1], 0, -1}}};

Compare all distinct pairs:

deleteSubcases[sols_] :=

With[{vars = # -> Unique[] & /@ Variables@sols},

Pick[sols,

Not@*Or @@@

Outer[

With[{unknowns = Variables[#2] /. vars},

#1 =!= #2 && unknowns =!= {} &&

Solve[#1 == (#2 /. vars) && unknowns âˆˆ Integers, unknowns] =!= {}] &,

sols, sols, 1]

]]

MatrixForm /@ deleteSubcases[sols] // Column

Oh, the style is a little bit difficult for such a novice in Mathematica as I am, but that really seems to work, thank you very much!!! I would like to ask you one more thing. How this code should be changed if all parameters are supposed to be integers? For example, solutions 2a+1 and 2a won’t be equivalent in this case.

– Hypsoline

May 5 ’15 at 11:10

@Hypsoline I wondered about that. Solve takes an optional 3rd argument that specifies a domain: Solve[eqn, vars, Integers]. That should work. Sorry about the style. It was late — the @@@ is worth getting used to; otherwise, is there something I can help with?

– Michael E2

May 5 ’15 at 11:39

I am sorry, probably it is not a very profound question, but… If one just substitute ` Solve[#1 == (#2 /. vars), Variables[#2] /. vars] ` with ` Solve[#1 == (#2 /. vars), Variables[#2] /. vars, Integers] ` in the code above, the output is not the same any more (as it should be) and consists of just one integral matrix.

– Hypsoline

May 5 ’15 at 11:51

Thank you! What about the style, could you please tell me what the part ` Not@*Or ` does?

– Hypsoline

May 5 ’15 at 11:54

@Hypsoline (1) Try Solve[#1 == (#2 /. vars) && (Variables[#2] /. vars) \[Element] Integers, Variables[#2] /. vars]. (2) Not@*Or is short for Composition[Not, Or] and equivalent to Not[Or[##]] &. This is Apply-ed via @@@ to each row of the table created by Outer.

– Michael E2

May 5 ’15 at 12:07

Suppose you have four solution matrices:

mysol =

{{{1, 0, a}, {0, b, 1 – a}, {0, 0, 0}},

{{1, 0, a}, {0, a, 1 – a}, {0, 0, 0}},

{{1, 0, 2 b}, {0, b, 2 – a}, {0, 0, 0}},

{{1, 0, a}, {0, b, 1 – b}, {0, 0, 0}}};

You can find the matrices that are equivalent (or degenerate) this way:

degens = Table[

If[Solve[mysol[[i]] == mysol[[j]], {a, b}] != {}, {i, j}, Null],

{i, 2, Length[mysol]}, {j, 1, i – 1}] // Quiet

(*

{{{2, 1}}, {Null, Null}, {{4, 1}, {4, 2}, {4, 3}}}

*)

This says that matrix 2 and matrix 1 can be equivalent (i.e., one can solve for bb as a function of aa), likewise matrix 4 and matrix 1, … and so on. A simpler way to see this is:

zz = Flatten[Select[degens, ! MemberQ[#, Null] &], 1]

(*

{{2, 1}, {4, 1}, {4, 2}, {4, 3}}

*)

It is instructive to view these relations as a graph:

ss = Graph[#[[1]] -> #[[2]] & /@ zz, VertexLabels -> “Name”]

This graph shows that the only nodes (matrices) that are truly independent are 1 and 3, i.e., they have no edge linking them.

You can calculate this explicitly this way (find the rows that have no non-zero entries):

Position[AdjacencyMatrix[Normal[Transpose[AdjacencyMatrix[ss]]]],

{0, 0, 0, 0}] // Quiet

(*

{{1,3}}

*)

Indeed, only matrices 1 and 3 are independent in the set.

I am sorry but I am not sure I’ve grasped the thing. First of all, if I am not terribly mistaken, the result in this case should be the list consisting of mysol[[1]], mysol[[3]] and mysol[[4]]. For any of these three types there is a solution which cannot be expressed as a solution of one of the other two types. For example, {{1, 0, -1}, {0, 1, 2}, {0, 0, 0}} is a solution of the first type and is not a solution of the third or the fourth type. My goal is to get all solutions but delete such excess specific cases as mysol[[2]] is for mysol[[1]].

– Hypsoline

May 4 ’15 at 23:20

The second point is that I do not understand why do you use “Solve[mysol[[i]] == mysol[[j]], {a, b}]”. It is quite strange. To my mind, one should treat parameters on the left side as though they have names which are different from the names of the parameters on the right side (and it can be so in the original problem!)

– Hypsoline

May 4 ’15 at 23:21