Linear Systems

• $A\mathbf{x}=\mathbf{b}$ is a linear system ($m$ equations, $n$ variables) over $\mathbb{F}$
• $A$ is $m\times n$ matrix, called the coefficient matrix of the system
• $\mathbf{x}$ is $n\times 1$ vector, called the variable vector
• $\mathbf{b}$ is $m\times 1$ vector, called the constant vector
  • If $\mathbf{b}=0$, then the system is homogeneous
• $(A|\mathbf{b})$ is the augmented matrix of the system
• The solution set of the system is the set of all $\mathbf{x}$ that satisfy the system, defined as $\text{Sol}(A,\mathbf{b})=\{\mathbf{x}\in {\mathbb{F}}^n\mid A\mathbf{x}=\mathbf{b}\}$
  • The solution set is either empty, a singleton, or infinite
  • The solution set is an affine subspace of ${\mathbb{F}}^n$
  • ${\mathbf{x}}_p\in \text{Sol}(A,\mathbf{b})⟹\text{Sol}(A,\mathbf{b})=\{{\mathbf{x}}_p+{\mathbf{x}}_h\mid {\mathbf{x}}_h\in \text{null}(A)\}$ (or shortly ${\mathbf{x}}_p+\text{null}(A)$)
    • That is, we have either, $\text{Sol}(A,\mathbf{b})=\varnothing$, or $\text{Sol}(A,\mathbf{b})={\mathbf{x}}_p+\text{null}(A)$
    • ${\mathbf{x}}_p$ is a particular solution of the system
    • ${\mathbf{x}}_h$ is any solution of the homogeneous system $A\mathbf{x}=0$
  • The system is consistent if its solution set is not empty
  • The system is inconsistent if its solution set is empty
  • The system is determined if its solution set is a singleton
  • The system has infinitely many solutions if its solution set is infinite
  • The solution set of a homogeneous system is called the null-space of $A$ and denoted by $\text{null}(A)$
    • $\text{null}(A)$ is a subspace of ${\mathbb{F}}^n$
    • $\mathbf{v},\mathbf{u}\in \text{null}(A)⟹\mathbf{v}+\mathbf{u}\in \text{null}(A)$
    • $\mathbf{v}\in \text{null}(A)⟹c\mathbf{v}\in \text{null}(A)$

Equivalence

• (d1.7.1) The following statements are equivalent:
  • The linear systems $A\mathbf{x}=\mathbf{b}$ and $C\mathbf{x}=\mathbf{d}$ are equivalent systems
  • $\text{Sol}(A,\mathbf{b})=\text{Sol}(C,\mathbf{d})$
  • The augmented matrices $[A|\mathbf{b}]$ and $[C|\mathbf{d}]$ are row equivalent
  • $\text{RREF}(A|\mathbf{b})=\text{RREF}(C|\mathbf{d})$

Augmented Matrix Characterization

Given $\mathbf{b}\in {\mathbb{F}}^m$ and a linear system $A\mathbf{x}=\mathbf{b}$ ($m$ equations, $n$ variables) over $\mathbb{F}$

Consistency

• The following statements are equivalent:
  • $A\mathbf{x}=\mathbf{b}$ is consistent
  • $\exists \mathbf{v}\in {\mathbb{F}}^n:A\mathbf{v}=\mathbf{b}$
  • (8.6.2; Rouché–Capelli theorem) $\rho ([A|\mathbf{b}])=\rho (A)$
  • $\text{REF}[A|\mathbf{b}]$ does not have a row of the form $[00\cdots 0|b]$ (where $b\ne 0$)
  • $\mathbf{b}$ is a linear combination of the colmuns of $A$
  • $\mathbf{b}\in \text{column-space}(A)$

Determined Case

• The following statements are equivalent:
  • The system $A\mathbf{x}=\mathbf{b}$ is determined
  • $\text{Sol}(A,\mathbf{b})$ is a singleton
  • $A\mathbf{x}=\mathbf{b}$ is consistent and $A$ has full column rank

Infinite Solutions Case

• The following statements are equivalent:
  • The system $A\mathbf{x}=\mathbf{b}$ has infinitely many solutions
  • $\text{Sol}(A,\mathbf{b})$ is an affine subspace of ${\mathbb{F}}^n$
  • $A\mathbf{x}=\mathbf{b}$ is consistent and $A$ has not full column rank

Inconsistency

• The following statements are equivalent:
  • The system $A\mathbf{x}=\mathbf{b}$ is inconsistent
  • $\text{Sol}(A,\mathbf{b})=\varnothing$
  • $\text{rank}(A)<\text{rank}([A|\mathbf{b}])$
  • $\text{REF}[A|\mathbf{b}]$ has a row of the form $[00\cdots 0|b]$ (where $b\ne 0$)
  • $\mathbf{b}\notin \text{column-space}(A)$

Homogeneous System

$A\mathbf{x}=0$

• Homogeneous system is always consistent
• if $m<n$, then it has infinitely many solutions

Infinite Solutions Case

• The following statements are equivalent
  • $A$ has not full column rank (i.e. $\text{rank}(A)<n$)
  • $A\mathbf{x}=0$ has a nontrivial solution
  • $A\mathbf{x}=0$ has infinitely many solutions
  • $A\mathbf{x}=0$ has at least one free variable

Determined Case

• The following statements are equivalent
  • $A\mathbf{x}=0$ has only the trivial solution
  • $A$ has full column rank

Coefficient Matrix Characterization

• The following statements are equivalent

  • For each $\mathbf{b}\in {\mathbb{F}}^m$, the system $A\mathbf{x}=\mathbf{b}$ is consistent
  • $A$ has full row rank

• A linear system is said to be overdetermined if it has more equations than unknowns ($m>n$)

  • if $m>n$ then there exists a vector $\mathbf{b}\in {\mathbb{R}}^m$ s.t. $A\mathbf{x}=\mathbf{b}$ is inconsistent

• A linear system is said to be underdetermined if it has more unknowns than equations ($m<n$)

  • if $m<n$ then for each vector $\mathbf{b}$ in ${\mathbb{R}}^m$ the system $A\mathbf{x}=\mathbf{b}$ is either inconsistent or has infinitely many solutions

Overdetermined systems are usually inconsistent, but not always

Underdetermined systems are usually consistent with infinitely many solutions, but not always

Square System (m=n)

• The following statements are equivalent:
  • $A$ is Invertible
  • For each $\text{b}$, the system $A\text{x}=\text{b}$ has unique solution. ($\text{x}=A^{-1}\text{b}$)
  • There exists $\text{b}$, such that the system $A\text{x}=\text{b}$ has a unique solution
  • $A\mathbf{x}=0⟹\mathbf{x}=0$
• The following statements are equivalent:
  • $A$ is singular
  • $A\mathbf{x}=0$ has non trivial solution
• (4.6.1) Cramer’s rule: if $A$ is inevitable, then, $\mathbf{x}=(x_1,\dots ,x_n)$, $x_i=\frac{\det (A_i)}{\det (A)}$, $i=1,\dots ,n$, where $A_i$ is the matrix formed by replacing the $i$-th column of $A$ by the column vector $\mathbf{b}$