# Solving $U \cdot x = b$ with triangular matrix $U$ - why should $U$ be a square matrix?

So, I noticed something weird while using a library math.js: there is a function called usolve, that is supposed to find some solution of the equation $U\cdot x = b$, where $U$ is an upper-triangular matrix. This function requires $U$ to be square matrix.

I did a bit of googling and it looks like other math-tools such as scipy or matlab also require the matrix to be square for solving such an equation.

Question: why is it so?

For me it looks like you can just do some fixing by adding zeros here and there and make a square matrix out of $U$, so this requirement is just there to annoy people serves no purpose.

UPD: I am going to make an update to this question explaining in details how backsub-method would work for an upper-triangular matrix of any size... Any time now.

• MathJax works in the title, don't you know? – Shaun Jul 14 '18 at 15:36
• @Shaun I know, but I prefer to not use MathJax in the title. Well, might as well change that. – mike239x Jul 14 '18 at 16:06
• If $U$ has more rows than columns then the system is (typically) overdetermined and has no solution. If $U$ has more columns than rows then the system is (typically) underdetermined and has many solutions. If $U$ is square then the system has (typically) a unique solution. – Michal Adamaszek Jul 14 '18 at 19:32
• @MichalAdamaszek if $U$ is square the system still may have either none or multiple solutions. If you additionally require $U$ to be of the full rank, then there is exactly one solution, otherwise there no guarantee. – mike239x Jul 15 '18 at 16:46
• Typically matrices are not square; on the other hand, a triangular matrix is square by definition. – egreg Jul 17 '18 at 15:10

As far as I know, a triangular matrix is square to begin with under the most common definitions. The condition of triangularity can be relaxed: sometimes a non-square matrix $A=[a_{ij}]$ with $a_{ij}=0$ for $i>j$ is called upper trapezoidal: This is the common form of a matrix after row-reduction.

If $U$ is a (square) triangular matrix, in order that the system $Ux=b$ is solvable for any $b$, $U$ must be invertible, which can be checked by it having non-zero diagonal elements. The condition when $U$ is only upper trapezoidal is that every row has a pivot (that is, it has full row rank).

Inverting an invertible (square) triangular matrix is computationally easy, which is the reason why row-reduction is so important in applications of linear algebra.

If U is not square, then you have 2 choices:

• Tall matrix (100 rows and 2 columns). Imagine a graph with 100 dots. And you need to express all the dots with an equation $bx + a$ which is a line. The only way it's possible is if all the dots are on the same line. But if they are not - you're screwed, so there is no general solution that could satisfy all 100 dots.
• Wide matrix (1 row and 2 columns). Suppose you have 1 dot on the graph - do you really need $bx + a$? No, you can express it with just $a$ or just $b$ or some other combination of $a$ and $b$. Therefore you can come up with many ways to arrange the variables to express your point. Meaning there are many solutions.

The tools that you're using are trying to find 1 solution which is not the case of the matrix is not squared.

• It is no surprise that using non-quare matrices you would lose $\exists !$ quantifier, but that doesn't explain why the software would actively disallow non-square matrices. The software could just raise an error in the first case if there is no solution, and return any valid solution in the second case. – mike239x Jul 15 '18 at 16:35
• It is even more weird because for the square matrices a priori it is not guaranteed there is exactly one solution... – mike239x Jul 15 '18 at 16:38
• In order to solve your equation, it needs to calculate inverse matrix. Which won't be possible in either case. If square matrix contains linearly dependant columns, then it will probably raise an error as well. – Stanislav Bashkyrtsev Jul 15 '18 at 17:37
• I am pretty sure this is not how it works and no inverse of the given matrix is calculated while solving, and it is not required for the matrix $U$ to be of full rank. – mike239x Jul 15 '18 at 21:53

Ok, I am just going to answer this from the perspective here of the QR algorithm and why R needs to be square. I think there may be different ones. I am going to write this out. Suppose $Ax = b$ then $QRx =b$ now. Gram-Schmidt works like this.

$$a_{1} = r_{11}q_{1}$$ $$a_{2} = r_{12}q_{1} + r_{22}q_{2}$$ $$a_{3} = r_{13}q_{1} + r_{23}q_{2} + r_{33}q_{3}$$ $$\vdots$$ $$a_{n} = r_{1n}q_{1} + r_{2n}q_{n} + \cdots + r_{nn}q_{n}$$

$$A = \tilde{Q}\tilde{R}$$

for when $m\geq n$ so if we have. $QRx=b \implies R =Q^{*}b$ the back sub-algorithm works like this.

function x = backsub(R,b)
% Backsub for upper triangular matrix.
[m,n] = size(R);
p = min(m,n);
x  = zeros(n,1);

for i=p:-1:1
% Look from bottom, assign to vector
r = b(i);
for j=(i+1):p
% Subtract off the difference
r = r-R(i,j)*x(j);
end
x(i) = r/R(i,i);
end

end


And $R$ looks like

$$R = \begin{bmatrix} r_{11} & r_{12} & \cdots & r_{1n} \\ & r_{22} & & \vdots \\ & & \ddots \\ & & & r_{nn} \end{bmatrix}$$

Back sub works by going to the diagonal and working backwards. If $m<n$ in the $QR$ you have more entries I believe.

• This method does work even if the matrix is not square. It can find a solution anyways. Moreover, the link you included doesn't say you need a square matrix. – mike239x Jul 16 '18 at 6:10
• The computer uses the QR decomp when it isn't square. math.stackexchange.com/questions/2836110/… – воитель Jul 16 '18 at 14:31
• Ok, look: imagine I got a non-square matrix $M$ and I want to solve $Mx = b$. I use QR decomp just as you told me. I get square matrix Q, and upper triangular matrix $R$, which is non-square. So to solve $QRx = b$ I need to solve $Rx = Q^Tb$ for non-square upper-triangular matrix $R$. How would I do that? I would need some implementation of usolve for non-square matrices! – mike239x Jul 16 '18 at 15:56
• @mike239x the $R$ matrix is a square matrix. Please see trefethan. Only the Q matrix may be non-square. – воитель Jul 16 '18 at 16:03
• Welp, either wikipedia is wrong, or you are. $Q$ is the orthogonal matrix, and hence also square-shaped. – mike239x Jul 16 '18 at 16:09