finite-dimensional linear problem

Let $L:U\rightarrow V$ be a linear mapping, and let $v\in V$ be given. When both the domain $U$ and codomain $V$ are finite-dimensional, a linear equation

L(u)=v,

where $u\in U$ is the unknown, can be solved by means of row reduction. To do so, we need to choose a basis $a_{1},\ldots,a_{m}$ of the domain $U$ , and a basis $b_{1},\ldots,b_{n}$ of the codomain $V$ . Let $M$ be the $n\times m$ transformation matrix of $L$ relative to these bases, and let $y\in\mathbb{R}^{n}$ be the coordinate vector of $v$ relative to the basis of $V$ . Expressing this in terms of matrix notation, we have

	$\displaystyle\begin{bmatrix}L(a_{1}),\ldots,L(a_{m})\end{bmatrix}=\begin{% bmatrix}b_{1},\ldots,b_{n}\end{bmatrix}\begin{bmatrix}M_{11}&\ldots&M_{1m}\\ \vdots&\ddots&\vdots\\ M_{n1}&\ldots&M_{nm}\end{bmatrix},$
	$\displaystyle v=\begin{bmatrix}b_{1},\ldots,b_{n}\end{bmatrix}\begin{bmatrix}y% _{1}\\ \vdots\\ y_{n}\end{bmatrix}$

We can now restate the abstract linear equation as the matrix-vector equation

Mx=y,

with $x\in\mathbb{R}^{m}$ unknown, or equivalently, as the following system of $n$ linear equations

\begin{array}[]{ccccl}M_{11}x_{1}+&\cdots&+M_{1m}\,x_{m}&=&y_{1}\\ \vdots&\ddots&\vdots&&\vdots\\ M_{n1}x_{1}+&\cdots&+M_{nm}\,x_{m}&=&y_{n}\end{array}

with $x_{1},\ldots,x_{m}$ unknown. Solutions $u\in U$ of the abstract linear equation $L(u)=v$ are in one-to-one correspondence with solutions of the matrix-vector equation $Mx=y$ . The correspondence is given by

u=\begin{bmatrix}a_{1},\ldots,a_{m}\end{bmatrix}\begin{bmatrix}x_{1}\\ \vdots\\ x_{m}\end{bmatrix}.

Note that the dimension of the domain is the number of variables, while the dimension of the codomain is the number of equations. The equation is called under-determined or over-determined depending on whether the former is greater than the latter, or vice versa. In general, over-determined systems are inconsistent, while under-determined ones have multiple solutions. However, this is a “rule of thumb” only, and exceptions are not hard to find. A full understanding of consistency, and multiple solutions relies on the notions of kernel, image, rank, and is described by the rank-nullity theorem.

Remark.

Elementary applications exclusively on the coefficient matrix and the right-hand vector, and neglect to mention the underlying linear mapping. This is unfortunate, because the concept of a linear equation is much more general than the traditional notion of “variables and equations”, and relies in an essential way on the idea of a linear mapping. See the example (http://planetmath.org/UnderDeterminedPolynomialInterpolation) on polynomial as a case in point. Polynomial interpolation is a linear problem, but one that is specified abstractly, rather than in terms of variables and equations.

Title	finite-dimensional linear problem
Canonical name	FinitedimensionalLinearProblem
Date of creation	2013-03-22 12:26:05
Last modified on	2013-03-22 12:26:05
Owner	rmilson (146)
Last modified by	rmilson (146)
Numerical id	12
Author	rmilson (146)
Entry type	Definition
Classification	msc 15A06
Related topic	LinearProblem
Related topic	RankNullityTheorem
Defines	system of linear equations