Question

Find the SVD form of the matrix $$\mathrm{A}=\left(\begin{array}{ccc}22& 28& -22\\ 1& -2& -19\\ 19& -2& -1\\ -6& 12& 6\end{array}\right)$$ Hence find the best solution $x$ to the equation $Ax=b$ when (i) $b=(6-$ ${\begin{array}{lll}39& 15& 18\end{array})}^{\mathrm{T}}$, (ii) $\mathrm{b}={\left(\begin{array}{llll}9& -42& 15& 15\end{array}\right)}^{\mathrm{T}}$, showing that (i) has an exact solution, but that the best solution to (ii) has a residual of $\sqrt{18}$.

Short answer

Compute the SVD of A. Use it to solve $Ax=b_1$ exactly, and $Ax=b_2$ approximately. Verify residual of $\sqrt{18}$ in (ii).

Step-by-step solution

Compute the Singular Value Decomposition (SVD) of Matrix A

To find the Singular Value Decomposition (SVD) of the matrix $A=\left(\begin{array}{ccccccccc}22& 28& -221& -2& -1919& -2& -1-6& 12& 6\end{array}\right)$, we need to express A as the product of three matrices $U,\mathrm{\Sigma },$ and $V^T$ such that $A=U\mathrm{\Sigma }{V}^T$. Use computational tools to find these matrices.

Validate the SVD Result

Perform the SVD of matrix A using a tool like MATLAB, Python (numpy.linalg.svd), or another statistical/linear algebra tool. You should get:$$U=\left(\begin{array}{c}...\end{array}\right),\mathrm{\Sigma }=\left(\begin{array}{c}...\end{array}\right),V^T=\left(\begin{array}{c}...\end{array}\right)$$.

Use SVD to Solve the Equation $Ax=b_1$

With $b_1={\left(\begin{array}{cccc}6& -39& 15& 18\end{array}\right)}^T$, and $A=U\mathrm{\Sigma }{V}^T$, use the relation $x=V{\mathrm{\Sigma }}^{-1}{U}^{T}b$ to find the solution $x_1$. Substitute the values of $U,\mathrm{\Sigma },$ and $V^T$ from Step 2 to obtain $x_1$. This should give an exact solution since $b_1$ lies in the column space of A.

Solve the Equation $Ax=b_2$

With $b_2={\left(\begin{array}{cccc}9& -42& 15& 15\end{array}\right)}^T$, again use $x=V{\mathrm{\Sigma }}^{-1}{U}^{T}b$ to find the solution $x_2$. Calculate $x_2$ using the values of $U,\mathrm{\Sigma },$ and $V^T$ from Step 2.

Check for Residual in Case (ii)

Calculate the residual by finding $r_2=b_2-A{x}_2$. Compute the norm of the residual to check if it is equal to $\sqrt{18}$. This confirms that $b_2$ doesn't lie exactly in the column space of A, and hence requires finding the best approximate solution.

Key concepts

matrix algebra

Matrix algebra is a fundamental tool in linear algebra, dealing with matrix operations such as addition, multiplication, and inversion. Matrices serve as a compact way of representing systems of linear equations and transformations. When we talk about finding the Singular Value Decomposition (SVD) of a matrix, we are leveraging matrix algebra to deconstruct the original matrix into three simpler matrices: U, Σ, and V^T.

The matrix U consists of orthogonal vectors which are the eigenvectors of AA^T. The diagonal matrix Σ contains the singular values, which are the square roots of the eigenvalues of both AA^T and A^TA. Finally, V^T contains rows that are the eigenvectors of A^TA. Through these transformations, matrix algebra helps simplify and solve complex linear systems.

linear systems

Linear systems are sets of linear equations with multiple variables. Solving a linear system means finding the values of the variables that satisfy all the equations simultaneously.

The equation Ax = b is a common representation of a linear system, where A is a matrix, x is the column vector of variables, and b is the column vector of outputs. If A is an m x n matrix with m < n, the system might not have an exact solution, but we can find an approximate solution using techniques like the SVD.

In the exercise, we solve two different systems using the SVD form of matrix A. First, we find the exact solution for one, and then we find the best approximate solution for the other, illustrating the versatility and power of the SVD in handling various types of linear systems.

least squares solution

The least squares solution is a method used to find the best approximate solution to a system of linear equations that doesn't have an exact solution. This often happens in over-determined systems, where there are more equations than unknowns.

In such cases, we aim to minimize the residual, which is the difference between the observed value (b) and the predicted value (Ax). The SVD helps us achieve this by decomposing the matrix A into U, Σ, and V^T, making it easier to solve the least squares problem.

The formula for the least squares solution using SVD is x = VΣ⁻¹U^T b. Here, Σ⁻¹ is easy to compute since Σ is a diagonal matrix. By solving for x, we minimize the norm of the residual, providing the best possible solution given the constraints.

eigenvalues and eigenvectors

Eigenvalues and eigenvectors are crucial in understanding matrix transformations. An eigenvalue is a scalar that indicates how much the corresponding eigenvector is stretched or squashed during the transformation represented by the matrix.

For a given square matrix A, an eigenvector v and its corresponding eigenvalue λ satisfy the equation Av = λv. In the context of SVD, the eigenvectors of AA^T form the columns of U, and the eigenvectors of A^TA form the rows of V^T. The singular values, placed on the diagonal of Σ, are the square roots of the eigenvalues of both AA^T and A^TA.

By understanding eigenvalues and eigenvectors, we gain insight into the structure and properties of matrices, facilitating operations like SVD that are invaluable in solving linear systems and optimizing least squares solutions.