# Why is dimension of solution space of homogeneous equations n-r?

This throws me off track completely - its like pushing me out of moving train.I am referring to page 65 of Shilov (Linear algebra).

The author clearly states that in Homogeneous system of linear equations:

1. If the coefficient matrix has order k x n (k -> number of equations, n -> number of unknowns)
2. r is rank of the matrix.

Then linear solution space has dimension n-r.

I would think if rank is r, then the number of linearly independent rows is r. So if xi denotes any solution for r+1st equation to kth equation, it should be totally describable by linearly independent solutions ri from i=1 to i=r (Again going by rank).

Yet, the dimension of solution space L is given by n-r.

Why?

Update: What's being said is starting to makes sense. I am probably mixing up the concept of linear independence of columns of basis minor matrix (rank r) with dimension of solution space.

I guess the fact that first r columns of coefficient matrix of rank r are linearly independent implies that other columns r+1 .... n is expressible in terms of r columns.

That gives us freedom to arbitrarily choose solutions cr+1...n for dependent column variables with solutions c1...r for linearly independent column elements uniquely determinable (By Cramers rule). This "freedom" manifests as dimension n-r of solution space. Does the above sound coherent?

Hans's remark is salient. The solution space is in some sense the degrees" of freedom you have in choosing your variables, or the dimension of the subspace in which solutions (for example $ax+by=0$, has en intire line of solutions, granted that $a,b\neq 0)$.

Here is another way to think about it, from a more linear-algebraic point of view. Depending on your background, it may be helpful.

A matrix $n \times k$ can be thought of as a linear transformation $\mathbb R^n \to \mathbb R^k$, in the sense that it takes as input $n$ vectors (variables) and outputs a $k$-dimensional vector.

The rank of a matrix is the dimension of the subspace that the image spans. In other words, $\mathbb R^n \to \mathbb R^k$ may not be surjective, all of the outputs could potentially lay on the same line, as in the case of $$A:= \begin{pmatrix}1 & 0\\0 & 0 \end{pmatrix}$$

So, the solutions to a bunch of equations are asking when is $$Ax =0$$ where $x \in \mathbb R^n$ and $0 \in \mathbb R^k$. The Rank Nullity theorem tells us that $\dim \ker A=n- \dim\mathrm{Im}A=n-r$

• thanks for your comments, could you please see my reply to Hans Lundmark below and comment? i appreciate your help in making me understand – Ace Oct 31 '17 at 16:19

Have you tried an example, say a single equation (not identically zero) with 100 unknowns? I hope you agree that there are 99 free parameters in the solution in that case, not just one. (All variables can do what they want, except that one of them will have to adapt its value to make sure the equation is satisfied.)

• that's totally in line with my mental model and it makes complete sense. Where I am tripping is if that one last variable is being determined then it is dependent on the other 99 variables. So the system has 99 degrees of freedom and hence a proportional 99 dimensions. What's wrong with my reasoning? – Ace Oct 31 '17 at 15:51
• Plus if that system is part of a larger system, then those 99 rows can potentially figure into basis minor of coefficient matrix correct? – Ace Oct 31 '17 at 15:52
• So wouldn't that mean that one variable is linear combination of others (dependent) and hence the basis are the first 99 variables? – Ace Oct 31 '17 at 16:06
• Yes, there are 99 degrees of freedom, so the solution space is 99-dimensional, which is exactly what the formula $n-r=100-1=99$ is saying. What you mean by “basis minor of coefficient matrix”, I don't know, and likewise for “the basis are the first 99 variables”. If one talks about a basis for the solution space, that means 99 linearly independent vectors in $\mathbb{R}^{100}$ such that any solution vector $(x_1,\dots,x_{100})$ is a linear combination of them. So the basis elements aren't “variables”. – Hans Lundmark Oct 31 '17 at 17:13
• Thanks, the main confusion happens when Shilov uses Basis Minor (Rank of coefficient matrix) in explaining dimension of solution space. Basis minor by definition are linearly independent vector columns (r number of columns), whereas solution space has dimension n-r. If r number of vectors at most are linearly independent, then the dimension of the space is r correct? That suggests that dimensionality of solution space is r. And no i am not confusing basis elements for variables. I assume they are set of all linearly independent solutions. – Ace Oct 31 '17 at 17:28