3
$\begingroup$

I'm reading a linear algebra textbook and I have some confusion about the concept of underdetermined systems $A\mathbf{x}=\mathbf{y}$:

  • First, we know that for each vector $\mathbf{y}$ in $\mathbb{R}^m$ the underdetermined linear system is either inconsistent or has infinitely many solutions. So are there some theorems that tell us when the system is inconsistent and when it has infinitely many solutions?

  • Second, if an underdetermined linear system has infinitely many solutions, is it guaranteed that a positive solution (all elements in $\mathbf{x}$ are positive) exists?

It would be very appreciated if anyone could give some explanation on them.

$\endgroup$
2
  • $\begingroup$ By determining the ranks of $A$ and $A$ concatenated with $y$ , you can actually decide whether there is a unique solution. If the matrix $A$ has size $m\times n$, then the solution is unique if and only if both ranks are equal to $n$. No solution exists if and only if the ranks have distinct values. $\endgroup$
    – Peter
    Oct 13 at 15:43
  • $\begingroup$ Concerning the second question : If all matrix elements are negative and the elements of $y$ are all positive, there obviously cannot exist a solution $x$ with only positive entries. $\endgroup$
    – Peter
    Oct 13 at 15:48
4
$\begingroup$

There is indeed a theorem:

The linear system $Ax=b$ has a solution if & only if the matrix $A$ and the augmented matrix $[A|b]$ have the same rank. If this is the case, the common rank is the codimension of the (affine) subspace of solutions.

$\endgroup$
2
  • 1
    $\begingroup$ Hi $\ddot\smile$, what is the codimension? $\endgroup$
    – Sebastiano
    Oct 13 at 21:30
  • 1
    $\begingroup$ The difference between the dimension of the ambient space and the dimension of the subspace. For instance, a hyperplane has codimension $1$. $\endgroup$
    – Bernard
    Oct 13 at 21:35
3
$\begingroup$

You can use row reduction to determine a basis for the subspace given by $Ax=0$. Then you have to check to see if $y$ is in the span of that subspace. A simple way to compute this is to verify that $A$ and $A$ concatenated with $y$ have the same rank by row reduction.

As for the positive values note that a change of basis can change the signs. For example in $\mathbb{R}^4$ if we consider the span of $(1,-1,0,0)$ and $(0,0,1,-1)$ with respect to the canonical basis we cannot separate the positive and negative parts with linear operations but if we choose these two vectors as basis vectors then you can express them using strictly positive coefficients.

$\endgroup$

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.