Solving a System of Equations without a Square Matrix

Question

I am new to linear algebra.

I have:

• a known Mx1 vector called y
• a known MxN vector called X
• an unknown Nx1 vector called a

such that:

$$ y = Xa $$

I also know that

• each row of X ($x1i ...x1N$, $x2i ...x2N$, etc.) is linearly independent
• M < N (i.e. there are more columns than rows in X)

How can I go about solving this system of equations? If the matrix were square, I think I could just invert X and solve accordingly for a. However, I know you cannot invert a non-square matrix. Intuitively I think there is a solution because the rows are both linearly independent and of a higher dimension than the number of elements in y. Any tips would be greatly appreciated!

Answer 1

There are a number of ways of looking at this, you're going to have to look for a least squares solution.

Multiply throughout by $X^{T}$, this will give you a square system which you can solve.

Answer 2

There is a solution because the rank of $A$ is $M$ (so the transformation is onto $\mathbb F^M$).

You could row reduce $A$ and then read off the solutions.

Answer 3

One way to understand it. If $y$ is a zero column, your system defines a vector subspace (called the null space of the system/matrix) of a $N$-dimensional space. Since $M < N$ and rows are linearly independent, the dimension of the null space is exactly $N - M$.

Let's denote null space of $X$ as $Null(X)$. If $y$ is not a null column, assuming $a_0$ is an arbitrary particular solution to your system, the set of solutions is precisely $\{a_0 + v \ | \ v \in Null(X)\}$.

Knowing this, you can simply perform Gaussian elimination on $X$, which should yield you a matrix with upper-left identity submatrix of dimension $M$. Unknown variables $x_{M+1}$ through $x_N$ are called free variables. The rest are known as dependent variables. The matrix you see now explicitly describes each dependent variable as a linear combination of free variables.

For each free variable, consider a column vector, where its entry equals 1 and all other free variable's entries equal 0. You can easily compute entries for dependent variables (see above).

This way you get $N - M$ vectors which are the basis for $Null(X)$.

Assuming you applied all Gaussian transformations to column vector $y$ as well, it is easy to see that it now contains a particular solution (call it $a_0$ for system X (consider all free variables to be 0).

Now that you have $a_0$ and $Null(X)$, you have the solution for the system.

Answer 4

The solution is obtained by finding the inverse of the matrix X. But it is not a square matrix and hence inverse cannot be computed using any of the conventional methods which are used to compute the inverse for nXn square matrices. So, the inverse of X is computed differently and it is called pseudo inverse or Moore-Penrose inverse. using this inverse you can compute the solution for

                          y = Xa            which gives
                          a = X'y           where X' = pseudoinverse of X

Pseudoinverse can be computed using Singular Value Decomposition (SVD) of a matrix. In SVD a matrix is expressed as the product of three matrices:

                           X = U*\Sigma*V^T

columns of U and V are the left singular and right singular vectors of X respectively and V^T stands for the transpose of V. \Sigma is the diagonal matrix whose entries contains the singular values of the matrix X.(Singular values are the absolute square roots of the non-zero eigenvalues of XX^T and X^TX) Pseudoinverse of X = X' is computed as follows

                           X' = V*(\Sigma)^(-1)*U^T

where \Sigma^(-1) = inverse of the diagonal matrix \sigma. it is easily evaluated by replacing diagonal entries with its corresponding reciprocals. U^T stands for the transpose of U Singular value decomposition of a matrix is done using Matlab with the help of the following command:

                       [U,S,V] = svd(X)

pseudoinverse or Moore-Penrose inverse is computed in Matlab using the following command:

                          X' = pinv(X)

For SVD refer https://en.wikipedia.org/wiki/Singular_value_decomposition For solving such equations using Moore-Penrose inverse or pseudo-inverse refer https://en.wikipedia.org/wiki/Moore%E2%80%93Penrose_inverse#Linear_least-squares