# 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 FinitedimensionalLinearProblem 2013-03-22 12:26:05 2013-03-22 12:26:05 rmilson (146) rmilson (146) 12 rmilson (146) Definition msc 15A06 LinearProblem RankNullityTheorem system of linear equations