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

Question

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.

Answer 1

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.

Answer 2

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.

Answer 3

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.