Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Let $X=\{x_1,\cdots,x_n\}$ be a set of variables in $\mathbb{R}$. Let $S_1$ be a set of linear equations of the form $a_1 x_1+\cdots+a_n x_n=b$ that are independent. Let $k_1=|S_1|<n$ where $|S_1|$ denotes the rank of $S_1$ (i.e., the number of independent equations). That is, $S_1$ does not contain enough equations to uniquely specify the values of the variables in $X$. How many other equations are needed to solve the system uniquely? The answer is $n - k_1$.

Let $M$ be a set of $n-k_1$ equations such that $S_1 \cup M$ is full rank (i.e., the system $S_1 \cup M$ can be solved uniquely). My first question is that how can one find a set $M$?

Let $S_2$ be a set of independent equations such that $|S_2|<n$ too. Now I want to find an $M$ such that both $S_1 \cup M$ and $S_2 \cup M$ are uniquely solvable. How can I find such an $M$? Note that $|M|$ must be $\ge \max(n-k_1,n-k_2)$.

What if we extend the question to $S_1,\cdots,S_m$ such that $S_1\cup M,\cdots,S_m\cup M$ are all uniquely solvable?

A partial answer is also appreciated.

share|cite|improve this question

Here is a reasonably easy algorithm if you already know some basic stuff about matrices:

Look at the coefficients matrix's rows as vectors in $\;\Bbb R^n\;$ :

$$A:=\{ v_1=(a_{11},\ldots,a_{1n})\;,\;v_2=(a_{21},\ldots,a_{2n})\,\ldots,v_k=(a_{k1},\ldots,a_{kn})\}\;\;(\text{where $\,k=k_1\;$ for simplicity of notation)}$$

Since you're given the equations are independent that means $\,A\,$ is a linearly independent set of vectors in $\,\Bbb R^n\;$ .

Well, now just "simply" complete the set $\,A\,$ to a basis of $\,\Bbb R^n\,$ and that's can do this by taking the matrix


and adding each time a new row $\,(b_1,\ldots,b_n)\,$ . Check whether this matrix is singular or not (for example, reducing this matrix and checking the row you added doesn't become all zeros!), and continue on until you get an $\,n\times n\$ regular matrix and voila!

share|cite|improve this answer
Thanks DonAntonio. "adding a new row ...", how do we choose a new row? Randomly? or you have a better idea? If it is chosen randomly, how do you extend your algorithm to more than one $S_i$? – Helium Jun 20 '13 at 9:19
If you have the actual vectors $\,v_1,...,v_k\,$ then simple inspection sometimes can be helpful to have an "educated guess" about what possible vector can we add. In general, though, it's not hard to prove that we can always add elements from a given, fixed basis, so you can always choose your vectors from the standard basis. This shall make things considerably easier. And the algorithm is: add first vector, then add another, then...etc. Of course, you can try to add two or more vectors simultaneously and then throw away the ones where we'll get a row of zeros and keep the other ones... – DonAntonio Jun 20 '13 at 9:23
Your algorithm is a actually a brute-force search for the answer which is quite inefficient. Consider this example: Assume we only use 0/1 coefficients and assume $S_i$ contains $n-1$ equations such that all of the variables except $x_i$ can be computed. There are exponentially many answers but only $M=\{x_1+x_2+\cdots+x_n=b\}$ is the correct one. So, brute-force searching is not efficient and as you mentioned, I think we need an "educated guess". – Helium Jun 20 '13 at 9:43

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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