Results 1 to 2 of 2

Thread: m equations, rank of m, a solution exists?

  1. #1
    Member Last_Singularity's Avatar
    Joined
    Dec 2008
    Posts
    157

    m equations, rank of m, a solution exists?

    Prove or provide counterexample: if the coefficient matrix of a system of $\displaystyle m$ linear equations in $\displaystyle n$ unknowns has rank $\displaystyle m$, then the system has a solution.

    I have an idea for the proof but I am not sure how to formalize it. Some advice, please?

    Here's the proof: let $\displaystyle A$ be the coefficient matrix in the system $\displaystyle Ax=b$. If $\displaystyle A$ has rank of $\displaystyle m$, then $\displaystyle n \geq m$. Say that's not true - then $\displaystyle n < m$, implying that the maximum rank of $\displaystyle A$ which equivalent to the max number of linearly independent columns, has a maximum of $\displaystyle n$, which is less than $\displaystyle m$ by assumption, meaning that the rank will never equal $\displaystyle m$. So we must have $\displaystyle n \geq m$. Then if the rank of $\displaystyle A$ is $\displaystyle m$, we can reduce the matrix [A|b] using row operations to a form [A'|b'] where all $\displaystyle x_i,i=1,...,m$ have coefficients of $\displaystyle 1$. Then a solution becomes $\displaystyle x_i=b'_i$ for $\displaystyle i=1,...,m$ and for $\displaystyle i=m+1,...,n$, we have $\displaystyle x_i = 0$.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    May 2008
    Posts
    2,295
    Thanks
    7
    Quote Originally Posted by Last_Singularity View Post
    Prove or provide counterexample: if the coefficient matrix of a system of $\displaystyle m$ linear equations in $\displaystyle n$ unknowns has rank $\displaystyle m$, then the system has a solution.

    I have an idea for the proof but I am not sure how to formalize it. Some advice, please?

    Here's the proof: let $\displaystyle A$ be the coefficient matrix in the system $\displaystyle Ax=b$. If $\displaystyle A$ has rank of $\displaystyle m$, then $\displaystyle n \geq m$. Say that's not true - then $\displaystyle n < m$, implying that the maximum rank of $\displaystyle A$ which equivalent to the max number of linearly independent columns, has a maximum of $\displaystyle n$, which is less than $\displaystyle m$ by assumption, meaning that the rank will never equal $\displaystyle m$. So we must have $\displaystyle n \geq m$. Then if the rank of $\displaystyle A$ is $\displaystyle m$, we can reduce the matrix [A|b] using row operations to a form [A'|b'] where all $\displaystyle x_i,i=1,...,m$ have coefficients of $\displaystyle 1$. Then a solution becomes $\displaystyle x_i=b'_i$ for $\displaystyle i=1,...,m$ and for $\displaystyle i=m+1,...,n$, we have $\displaystyle x_i = 0$.
    i guess that's fine. i'd solve the problem like this: suppose the entries of $\displaystyle A$ come from a field $\displaystyle F.$ let $\displaystyle v_1, \cdots , v_n \in F^m$ be the columns of $\displaystyle A.$ without loss of generality we may assume that $\displaystyle v_1, \cdots , v_m$

    are linearly independent. now, since $\displaystyle \dim_F F^m = m,$ the vectors $\displaystyle v_1, \cdots , v_m$ span $\displaystyle F^m.$ so if $\displaystyle b \in F^n,$ then $\displaystyle b=c_1v_1 + \cdots + c_m v_m,$ for some $\displaystyle c_j \in F.$ let $\displaystyle x_j = c_j$ for $\displaystyle 1 \leq j \leq m$ and $\displaystyle x_j = 0$ otherwise.

    clearly the $\displaystyle n \times 1$ vector $\displaystyle x$ with the entries $\displaystyle x_j$ satisfies $\displaystyle Ax=b.$
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 4
    Last Post: Nov 22nd 2011, 05:23 PM
  2. Rank of matrices and system of linear equations
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: Nov 24th 2010, 09:06 AM
  3. Prove solution exists
    Posted in the Differential Geometry Forum
    Replies: 2
    Last Post: Nov 4th 2010, 08:29 PM
  4. Replies: 1
    Last Post: Mar 24th 2010, 12:14 AM
  5. Replies: 3
    Last Post: Feb 8th 2010, 05:58 PM

Search Tags


/mathhelpforum @mathhelpforum