2
$\begingroup$

Suppose that I have a large system of linear equations, mostly of the form$$A+B+C=D$$where each letter, representing a variable, has coefficient one. Each equation can have any number of variables.

Now, in this system, certain variables are "suppressed", and certain ones are "unsuppressed". A unsuppressed variable is one whose value is set as a constant, while suppressed variables can hold any value that satisfies all of the equations.

For example, in the above equation, if $A$ and $D$ are suppressed, but $B,C$ are unsuppressed, with values of $B=2$ and $C=3$, the equation will become $$A+5=D$$The issue is, with certain variables set as unsuppressed, other variables can become "solvable", i.e., have a unique solution. When this happens, the suppressed variable is essentially an unsuppressed variable, which is not a desirable outcome.

So, my goal is to find the minimal set of unsuppressed variables, that if I make them suppressed, there would be no suppressed variables with unique solutions.

Progress so Far

I've been able to compute the right nullspace of the coefficient matrix representation of the system of equations, which allows me to find the variables with unique solutions. I also calculate the Moore Penrose pseudoinverse of the coefficient matrix to determine which equations are used to "solve" a given suppressed variable.

Any thoughts? References to linear algebra texts that could help me?

Example

In the following system of equations \begin{align} A+B+C+D=5\\A+B+C+D+E=7 \end{align}

It's obvious that the system as a whole does not have any unique solutions. However, variable $E$ definitely does (i.e., $E=2$). This is a pretty silly example, but demonstrates why simply finding the rank of the system is not sufficient.

$\endgroup$
  • 3
    $\begingroup$ Howm about you use standard terminology instead of a made-up terminology that doesn't even make sense? What you call "suppressed" is what "variable" means. What you call "unsuppressed" is normally called a parameter. If you don't want to have a unique solution, then you need at least one more variable (not parameters) than you have linearly independent equations. If there is a subset of the equations whose variables are all used only in that subset of the equations, then that subset must also involve at least one more variable than equations. $\endgroup$ – Paul Sinclair Sep 13 '18 at 3:52
  • 1
    $\begingroup$ @PaulSinclair Sorry for not knowing the correct terminology. However, I do believe in your hurry to comment, you've misread parts of my question. I don't want any individual variable to have a unique solution. A system can not have a unique solution, but a variable in it definitely can. $\endgroup$ – Don Thousand Sep 13 '18 at 4:00
  • $\begingroup$ @PaulSinclair I've added an example that, under the conditions you've provided, would be okayed, but clearly demonstrates that there is a problem. $\endgroup$ – Don Thousand Sep 13 '18 at 5:05
  • $\begingroup$ Moreover, as I said, I already have a way to compute those variables with unique solutions. I just need help finding ways to avoid them having them. $\endgroup$ – Don Thousand Sep 13 '18 at 5:05
  • $\begingroup$ And I've told you. You have to have at least one more variable than indepedent equation. If it is okay for some of the variables to be uniquely determined, then you can ignore the comments about subsets of the variables and subsets of the equations. But a system of $n$ independent equations in $n$ variables will always have a unique solution, while $n-1$ independent equations in $n$ variables will not have a unique solution. You can only solve it in terms of the value of one of the variables, which can be set freely. $\endgroup$ – Paul Sinclair Sep 14 '18 at 1:06
1
$\begingroup$

Let me rephrase the problem statement as I'm understanding it, in order to avoid unnecessary ambiguity:

We are looking for an algorithm that is given input consisting of three parts:

  • A set of $n$ variables named $X_i$ with $1\leq i\leq n$ (variables represent numbers of some kind; e.g. real numbers).
  • A set of $m$ linear relations of the form $\sum\limits_{i=1}^n c_{j,i}X_i = B_j$, where $1\leq j\leq m$ and $B_j$ is a number and $c_{j,i}\in\{0,1\}$ (i.e. every variable can either appear with coefficient $1$ or not appear at all).
  • A set of $n$ conditions, which, for each $1\leq i\leq n$ specify that variable $X_i$ is either unrestricted ("suppressed" in the original problem statement), or give it a fixed value $D_i$ (the "unsuppressed" ones). These conditions can be equivalently represented as a system of equations of the form $X_k=D_k$ where $k$ ranges over some subset of all variables.

We'll call a set of conditions good if combining this set of conditions with the set of relations results in a system of linear equations in which the value of no variable can be determined uniquely, apart from those appearing in the conditions already.

The algorithm should output the smallest (in terms of cardinality) subset of the set of conditions to be removed, so that the set of remaining conditions is good. If no such subset exists (i.e. if the set of relations determines some variable uniquely already), the algorithm should point this fact out too.

As it turns out, even the quite restricted form of relations used as input to this algorithm is already strong enough to express some difficult problems. In particular, consider the set cover problem, which is known to be NP-complete. In this problem, we are given a system $\mathbb{S}$ of sets $\mathbb{S}=\{S_1,S_2,\ldots,S_t\}$, union $U$ of which consists of $m$ elements ($U=\{e_1,e_2,\ldots,e_m\}$. We are looking for the smallest (again, in terms of cardinality) subsystem of this system whose union is still $U$.

Now, let's take this input to the Set-Cover problem and transform it as follows:

  • We will have $(m+t)$ variables, named $E_i$ with $\leq i\leq m$ (they will correspond to elements of $U$) and $P_j$ with $1\leq j\leq t$ (which will correspond to sets $S_j$). We'll let the variables range over integers, but that particular choice is not really much unimportant.
  • For element $e_i\in U$, we will create one relation of the form $$E_i+\sum_{e_i\in S_j}P_j=0$$
  • For each set $S_j$, we will add one condition of the form $P_j=0$ (the variables $E_i$ not get any conditions associated with them).

Clearly, if we combine all the relations and conditions, all $E_i$ will be uniquely determined to be equal to zero. We can also make a simple observation: In order for $E_i$ not to be uniquely determined, at least one of $P_j$ with $e_i\in S_j$ must be removed from the set of conditions. On the other hand, since each $E_i$ only appear in a single relation, this is actually also sufficient!

In the original set-cover language, this translates to "for each element $e_i\in U$, at least one $S_j$ containing it must be selected" which is precisely the definition of a set cover! Finding the minimal set of conditions-to-be-removed is therefore the same as finding the minimal set-cover and thus also solving an NP-complete problem (our transformation of inputs is polynomial in size).

In other words, we may need to either restrict the relations/conditions even further (so that they would be insufficient to represent the inputs to set-cover) or to allow imperfect solutions for the problem (e.g. possibly removing twice as many conditions as was strictly necessary)... or accept that the problem may not have an efficient solution (of course, heuristics can still lead to solutions quite quickly, in particular in "practical" cases).

$\endgroup$
  • $\begingroup$ Well, first off, thank you for taking the time to provide such a detailed response! I'll read through your answer a few times and let you know what I think. $\endgroup$ – Don Thousand Sep 25 '18 at 15:51
  • $\begingroup$ Enjoy your +100 bounty! $\endgroup$ – Don Thousand Sep 25 '18 at 16:00
  • $\begingroup$ I hope I have not made some silly mistake; the answer is so long precisely to avoid accidentally skipping over some detail... but one can never be sure. $\endgroup$ – Peter Košinár Sep 25 '18 at 16:11
  • $\begingroup$ I'm going to do the math out when I'm back from work, so I'll let you know if I find any flaws $\endgroup$ – Don Thousand Sep 25 '18 at 16:12
  • $\begingroup$ Do you mind going to the chat again? I have some questions $\endgroup$ – Don Thousand Sep 25 '18 at 22:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.