# Algorithm to check Gibbs' Phase Rule

I am looking for an algorithm to solve the following problem. I am unsure whether to post this in computational science or here, but since this is an algorithm I thought I would try here first.

I have a set of species made from a number of components.
Let's number each component $$0, 1, 2 ... n$$.
So now each species can be described as a set of these components. Each species is unique.

I am given a set of species, and I need to check whether any subset of these species fulfills the following condition: that the number of species in this subset is greater than the number of unique components in this subset.

For example: the set of species {[0, 1, 2], [0, 2], [1, 2], [0, 1]} fulfills the criterion, as the set has 4 species and 3 unique components. The set of species {[0, 1, 2], [0, 2], [1, 2], [0,1], [3,4]} also fulfills the criterion, as a subset of the set fulfills the criterion. The system {[0, 1, 2], [0, 2]} does not fulfill the criterion, as there are 2 species and 3 unique components.
In case it is relevant: there can be many species and components (20) but the number of components per species remains relatively small (2-5)

An easier version of this problem is also of interest to me: I have system which I know does not fulfill the criterion. The question is: if I add this species, will it fulfill the criterion?

This problem is equivalent to determining if a system of equations is over determined.

Edit: The criterion is equivalent to checking if the Gibbs Phase Rule is being violated in a system with only pure solid phases with at least 1 degree of freedom in addition to pressure and temperature. In this situation the number of phases is equal to the number of solids. There has a 0 or positive number of degrees of freedom left in the system or it becomes over constrained, so $$0 \geq \text{number of components} - \text{number of species}$$

• – D.W.
Jun 28 '20 at 3:42
• What is the most blunt algorithm that comes to your mind? What is your assessment of it's resource requirements? Jun 28 '20 at 8:06
• (Can you please make the connection to Gibbs' Phase Rule?) Jun 28 '20 at 8:06
• added connection to overdetermined system of equations Jun 28 '20 at 15:10
• I am wondering whether this might be a way to do it en.wikipedia.org/wiki/Rouch%C3%A9%E2%80%93Capelli_theorem Jun 28 '20 at 15:59

As we are talking about (usually) solids, this system of equations looks like $$K=A^nB^m...$$
If we take the log of both sides, this can be simplified to $$\log{k}=n\log{A}+m\log{B}...$$.
If we substitute $$a=\log{A}, b=\log{B}$$ then this becomes a system of linear equations $$\log{k}=n*a+m*b...$$
In the first example: {[0, 1, 2], [0, 2], [1, 2]} can be represented as the matrix $$\begin{bmatrix} 1 & 1 & 1\\ 1 & 0 & 1\\ 0 & 1 & 1\\ 0 & 1 & 0 \end{bmatrix}$$ Which has a rank deficiency, therefore is overdetermined.