Question about linear systems of equations

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.

-

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 all...you can do this by taking the matrix

$$\begin{pmatrix}a_{11}&a_{12}&\ldots&a_{1n}\\a_{21}&a_{22}&\ldots&a_{2n}\\\ldots&\ldots&\ldots&\ldots\\a_{k1}&a_{k2}&\ldots&a_{kn}\end{pmatrix}$$

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!

-
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