1
$\begingroup$

I encountered this problem in one of my linear algebra homeworks (Linear Algebra with Applications 5th Ed 1.3.44):

Consider a $n \times m$ matrix $A$, such that $n > m$. Show there is a vector $b$ in $\mathbb{R}^{n}$ such that the system $Ax=b$ is inconsistent.

I have a strong intuition as to why this is true, because the transformation matrix maps a vector in $\mathbb{R}^{m}$ to $\mathbb{R}^{n}$, so it is going from a lower dimension to a higher. When the $m$ components in $x$ vary, they would at most be parameterizing an $m$-dimensional subspace in $\mathbb{R}^{n}$. However, my "proof" (which is included below, feels very handwavey and sloppy. It may also be incorrect in a number of places. I'd appreciate it if I could get some pointers on how to formalize proofs of this type a little more, so they are rigorous enough to write on a homework/test, and maybe an example with this example.

My proof:

Consider the case where $A$ has at least $m$ linearly independent row-vectors. Using elementary row operations, rearrange $A$ to $A'$, so these $m$ row vectors are the first $m$ rows. $b'$ will refer to the vector $b$ under the same rearrangement of rows. If we place the first $m$ rows in reduced row ecchelon form using only elementary operations with the first $m$ rows, the augmented matrix $[A'|b']$ will have the following form, where $x_{i}$ is the $i$-th element of the solution vector $x$.

\begin{bmatrix} 1 & 0 & \dots & 0 & x_{1} \\ 0 & 1 & \dots & 0 & x_{2}\\ \vdots & \vdots & \ddots & \vdots & \vdots \\ 0 & 0 & \dots & 1 & x_{m} \\ a'_{m+1, 1} & a'_{m+1, 2} & \dots & a'_{m+1, m} & b'_{m+1} \\ \vdots & \vdots & \ddots & \vdots & \vdots \\ a'_{n,1} & a'_{n, 2} & \dots & a'_{n,m} & b'_{n} \end{bmatrix}

Now consider the $m+1$th row. To eliminate coefficients in this row, it would mean that $x_{m+1} = b'_{m+1} - $$\sum_{i=1}^{m} x_{i}\cdot a_{m+1,i}$, because to eliminate each coefficient would involve scaling by $a_{m+1,i}$ and then subtracting. The system is inconsistent for all $x_{m+1} \neq 0$, so we then choose any $b'_{m+1}$ for which this inequality holds, there are infinitely many, to find $b'$ which makes $A'x=b'$ inconsistent. Then, unswap the rows to make our $b'$ back into $b$ and we have found a vector which makes our system inconsistent.

$\endgroup$
  • $\begingroup$ Depending on what you can use: Assume no such $b$ exists. Then for each standard base vector $e_i$, $1\le i\le n$, we find at least one $x_i\in \Bbb R^n$ such that $Ax_i=e_i$. If $\sum c_ix_i=0$ for some numbers $c_i$, then $$\sum c_ie_i=\sum c_iAx_i=\sum Ac_ix_i=A\sum c_ix_i=A0=0.$$ As the $e_i$ are linearly independent, we conclude that all $c_i$ are $=0$. This shows that the $n$ vectors $x_i\in \Bbb R^m$ are linearly independent, contradiction. $\endgroup$ – Hagen von Eitzen May 25 '18 at 15:26
1
$\begingroup$

I would structure your argument like this. First, let $\bar{A}$ be the row-reduced Echelon form of $A$, so that $$\bar{A} = E_1 E_2\cdots E_k A$$ for elementary row operations $E_k$.

1) Can you exhibit a concrete $\bar{b}$ for which the row-reduced system $\bar{A}x = \bar{b}$ has no solution?

2) Can you use the answer to (1) to construct a $b$ for which $Ax=b$ has no solution?

$\endgroup$
1
$\begingroup$

Hint: how many pivot positions can the reduced echelon form of $A$ have? What does this say about the rank of $A$?

$\endgroup$
1
$\begingroup$

Hint: As a different approach, the equation $Ax=b$ has a solution (i.e., is consistent) iff $b$ is an element of the column space (range) of $A$. What can you say about the dimension of this space?

$\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.