1
$\begingroup$

Here is a problem I was looking at: Let production of Steel, Coal and electric power be $P_s, P_c$ and $P_e$ respectively. Their output (in column) and consumption (in row) are given:

$$ \begin{array}{|l|c|c|c|} \hline & Steel & Coal & Electricity \\ \hline Steel & 0.1 & 0.1 & 0.5 \\ Coal & 0.3 & 0.2 & 0.4 \\ Electricity & 0.6 & 0.7 & 0.1 \\ \hline \end{array} $$

To find equilibrium solution following system of equations is formed:

$$ \underbrace{\begin{pmatrix} -0.9 & 0.1 & 0.5 \\ 0.3 & -0.8 & 0.4 \\ 0.6 & 0.7 & -0.9 \end{pmatrix}}_A \begin{pmatrix} P_s \\ P_c \\ P_e \end{pmatrix} = \underbrace{\begin{pmatrix} 0 \\ 0 \\ 0 \end{pmatrix}}_b $$

Neither of $P=A^{-1}b$ and $P=A^+b$ works, so they've come up with SVD to produce a solution. To find $A=U\Sigma V^T$ following code is used:

A = [-0.9  0.1  0.5; 
      0.3 -0.8  0.4; 
      0.6  0.7 -0.9];

sigma1 = A*A'; sigma2 = A'*A;
U = eye(3); V = eye(3);

for i = 1:15
    [Q1,R1] = qr(sigma1);
    [Q2,R2] = qr(sigma2);
    U  = U * Q1; sigma1 = R1 * Q1;
    V  = V * Q2; sigma2 = R2 * Q2;
end

S = diag(diag(sigma1)); S = sqrt(S);
U = round(U,5); Sigma = round(S,5); V = round(V,5); 

With these $U,\Sigma$ and $V$ I get $U\Sigma V^T=-A$. To get correct result I've to multiply $V$ or $U$ by $-1$. With 15 iteration $U,\Sigma$ and $V$ are:

$$ \underbrace{\begin{pmatrix} -0.4852 & 0.6567 & 0.5774 \\ -0.3262 & -0.7485 & 0.5774 \\ 0.8113 & 0.0918 & 0.5774 \end{pmatrix}}_U\: \underbrace{\begin{pmatrix} 1.5836 & & \\ & 1.0547 & \\ & & 0 \end{pmatrix}}_{\Sigma}\: \underbrace{\begin{pmatrix} -0.5214 & 0.7211 & 0.4563 \\ -0.4928 & -0.6910 & 0.5289 \\ 0.6967 & 0.0509 & 0.7156 \end{pmatrix}}_V $$ If I change for i = 1:15 to for i = 1:115 and type U, Sigma and V in command window I get same thing but when I multiply $U\Sigma V^T$ I get:

$$ \underbrace{\begin{pmatrix} 0.9000 & -0.1000 & -0.5000 \\ -0.3000 & 0.8000 & -0.4000 \\ -0.6000 & -0.7000 & 0.9000 \end{pmatrix}}_{\texttt{for i = 1:15}}\quad\quad \underbrace{\begin{pmatrix} -0.0989 & 0.8572 & -0.5705 \\ 0.8385 & -0.2910 & -0.3197 \\ -0.7396 & -0.5662 & 0.8901 \end{pmatrix}}_{\texttt{for i = 1:115}} $$

Q1: What is the problem?

To find a solution last column of $V$ is chosen and normalized: $$ P= \frac{1}{0.7156} \begin{pmatrix} 0.4563 \\ 0.5289 \\ 0.7156 \end{pmatrix} = \begin{pmatrix} 0.6377 \\ 0.7391 \\ 1.0000 \end{pmatrix} $$

Q2: Why to choose last column of $V$?

Q3: Can I get same solution using $U$?

Q4: It is not unique and not least-square solution, What it is?

$\endgroup$
  • $\begingroup$ @Moo Can it be solved by Gaussian Elimination? If I use rational numbers, results are same. How to use infinite precision? $\endgroup$ – Emon Haque May 7 '17 at 13:20
  • $\begingroup$ @Moo, Here Gaussian Elimination probably they have used Eigenvalue Decomposition. SVD is similar to that. $\endgroup$ – Emon Haque May 7 '17 at 13:49
  • $\begingroup$ Instead of doing it one by one by hand, you should use elementary matrices for multiple row operation in a single shot, that is easier. @Moo $\endgroup$ – Emon Haque May 7 '17 at 14:31
1
$\begingroup$

A similar conundrum is discussed here: Query about the Moore Penrose pseudoinverse method. On to your question.

Existence

Given the matrix $$ \mathbf{A} = \frac{1}{10} \left[ \begin{array}{rrr} -9 & 1 & 5 \\ 3 & -2 & 4 \\ 6 & 7 & -1 \\ \end{array} \right] $$ and the data vector $$ b = \left[ \begin{array}{c} 0 \\ 0 \\ 0 \\ \end{array} \right] $$ what can we say about the linear system $$ \mathbf{A} x = b? $$

Using Gauss-Jordan elimination, $$ \begin{align} \left[ \begin{array}{c} \mathbf{A} & \mathbf{I}_{3} \end{array} \right] % &\mapsto % \left[ \begin{array}{c} \mathbf{E_{A}} & \mathbf{R} \end{array} \right] \\ %% \left[ \begin{array}{rrr|ccc} -\frac{9}{10} & \frac{1}{10} & \frac{1}{2} & 1 & 0 & 0 \\ \frac{3}{10} & -\frac{1}{5} & \frac{2}{5} & 0 & 1 & 0 \\ \frac{3}{5} & \frac{7}{10} & -\frac{1}{10} & 0 & 0 & 1 \\ \end{array} \right] % &\mapsto % \left[ \begin{array}{ccc|rrr} 1 & 0 & 0 & -\frac{130}{213} & \frac{60}{71} & \frac{70}{213} \\ 0 & 1 & 0 & \frac{45}{71} & -\frac{35}{71} & \frac{85}{71} \\ 0 & 0 & 1 & \frac{55}{71} & \frac{115}{71} & \frac{25}{71} \\ \end{array} \right] \tag{1} % \end{align} $$

Conclusion: All columns are fundamental. The matrix has full rank. The nullspace is trivial: $$\mathcal{N}\left( \mathbf{A}^{*} \right)=\emptyset$$

A nontrivial solution to the homogeneous equation does not exist. Solving the equation $\mathbf{A}x=\mathbf{0}$ is tantamount to asking for a vector in the nullspace. There are no such nontrivial vectors.

The existence drum is beaten often and loudly here on MSE:

Exact solution of overdetermined linear system

Existence of least squares solution to Ax=b

Unique least square solutions

Is a least squares solution to $Ax=b$ necessarily unique

Let $A$ be an 8 x 5 matrix of rank 3, and let $b$ be a nonzero vector in $N(A^{})$. Show $Ax=b$ must be inconsistent.

null space of a matrix for a matrix with a 0 column

Why does $A^{T}Ax=A^{T}b$ have infinitely many solution algebraically when $A$ has dependent columns?

Will 2 linear equations with 2 unknowns always have a solution?

When does the least squares solution exist?

SVD

$$ \mathbf{A} = \mathbf{U} \, \mathbf{S} \, \mathbf{V}^{*} \tag{2} $$

To clear up confusion of building the SVD, the steps are detailed.

  1. Construct the product matrix $\mathbf{A}^{*} \mathbf{A}$.
  2. Resolve eigensystem of product matrix: Construct $S$, $V$.
  3. Using $(2)$, construct $\mathbf{U} = \mathbf{A} \mathbf{V} \mathbf{S}^{-1}$.

1 Product matrix

$$ \mathbf{A}^{*} \mathbf{A} = \left[ \begin{array}{rrr} 1.26 & 0.27 & -0.39 \\ 0.27 & 0.54 & -0.10 \\ -0.39 & -0.10 & 0.42 \\ \end{array} \right] $$

2 Eigensystem decomposition

Eigenvalues: $$ \lambda \left( \mathbf{A}^{*}\mathbf{A} \right) = \left\{ 1.49952 , 0.453789 , 0.266694 \right\} $$ The singular values are computed using $$ \sigma = \lambda \left( \mathbf{A}^{*}\mathbf{A} \right) $$ Construct the $\mathbf{S}$ matrix: $$ \mathbf{S} = \left[ \begin{array}{ccc} 1.22455 & 0 & 0 \\ 0 & 0.673639 & 0 \\ 0 & 0 & 0.516425 \\ \end{array} \right] $$

Eigenvectors: $$ v_{1} = \left[ \begin{array}{l} -0.892021 \\ -0.287368 \\ \phantom{-}0.348883 \\ \end{array} \right], \quad % v_{2} = \left[ \begin{array}{l} \phantom{-} 0.256905 \\ -0.957414 \\ -0.131749 \end{array} \right], \quad % v_{3} = \left[ \begin{array}{l} \phantom{-} 0.371886 \\ -0.0278925 \\ \phantom{-} 0.927859 \end{array} \right] % $$ Construct the matrix $\mathbf{V}$, an orthonormal span for the row space: $$ \mathbf{V} = \left[ \begin{array}{ccc} \frac{v_{1}}{\lVert v_{1} \rVert} & \frac{v_{1}}{\lVert v_{2} \rVert} & \frac{v_{1}}{\lVert v_{3} \rVert} \end{array} \right] = \left[ \begin{array}{lll} -0.892021 & \phantom{-}0.256905 & \phantom{-}0.371886 \\ -0.287368 & -0.957414 & -0.0278925 \\ \phantom{-}0.348883 & -0.131749 & \phantom{-}0.927859 \\ \end{array} \right] $$

3 Column space matrix

$$ \mathbf{U} = \mathbf{A} \mathbf{V} \mathbf{S}^{-1} = \left[ \begin{array}{llc} \phantom{-}0.774591 & -0.583147 & 0.244844 \\ -0.0576372 & \phantom{-}0.320431 & 0.945517 \\ -0.629831 & -0.746501 & 0.214592 \\ \end{array} \right] $$

Moore-Penrose Pseudoinverse

The pseudoinverse is easily assembled using the SVD decomposition matrices.

$$ \mathbf{A}^{+} = \mathbf{V} \, \mathbf{S}^{-1} \, \mathbf{U}^{*} = \left[ \begin{array}{llc} -0.610329 & \phantom{-}0.84507 & 0.328638 \\ \phantom{-}0.633803 & -0.492958 & 1.19718 \\ \phantom{-}0.774648 & \phantom{-}1.61972 & 0.352113 \\ \end{array} \right] \tag{2} $$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.