Mixing
Solving $U cdot x = b$ with triangular matrix $U$ - why should $U$ be a square matrix?
Clash Royale CLAN TAG#URR8PPP
up vote
1
down vote
favorite
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 $Ucdot 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.
linear-algebra soft-question matrix-equations
asked Jul 14 at 15:31
mike239x
390111
 |Â
show 4 more comments
up vote
1
down vote
favorite
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 $Ucdot 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.
linear-algebra soft-question matrix-equations
asked Jul 14 at 15:31
mike239x
390111
MathJax works in the title, don't you know?
– Shaun
Jul 14 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 at 16:06
1
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 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 at 16:46
1
Typically matrices are not square; on the other hand, a triangular matrix is square by definition.
– egreg
Jul 17 at 15:10
 |Â
show 4 more comments
up vote
1
down vote
favorite
up vote
1
down vote
favorite
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 $Ucdot 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.
linear-algebra soft-question matrix-equations
asked Jul 14 at 15:31
mike239x
390111
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 $Ucdot 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.
linear-algebra soft-question matrix-equations
asked Jul 14 at 15:31
mike239x
390111
edited Jul 16 at 17:10
asked Jul 14 at 15:31
mike239x
390111
asked Jul 14 at 15:31
mike239x
390111
asked Jul 14 at 15:31
mike239x
390111
390111
MathJax works in the title, don't you know?
– Shaun
Jul 14 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 at 16:06
1
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 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 at 16:46
1
Typically matrices are not square; on the other hand, a triangular matrix is square by definition.
– egreg
Jul 17 at 15:10
 |Â
show 4 more comments
MathJax works in the title, don't you know?
– Shaun
Jul 14 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 at 16:06
1
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 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 at 16:46
1
Typically matrices are not square; on the other hand, a triangular matrix is square by definition.
– egreg
Jul 17 at 15:10
MathJax works in the title, don't you know?
– Shaun
Jul 14 at 15:36
MathJax works in the title, don't you know?
– Shaun
Jul 14 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 at 16:06
@Shaun I know, but I prefer to not use MathJax in the title. Well, might as well change that.
– mike239x
Jul 14 at 16:06
1
1
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 at 19:32
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 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 at 16:46
@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 at 16:46
1
1
Typically matrices are not square; on the other hand, a triangular matrix is square by definition.
– egreg
Jul 17 at 15:10
Typically matrices are not square; on the other hand, a triangular matrix is square by definition.
– egreg
Jul 17 at 15:10
 |Â
show 4 more comments
3 Answers
3
active
oldest
votes
up vote
1
down vote
accepted
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.
answered Jul 18 at 21:00
egreg
164k1180187
add a comment |Â
up vote
0
down vote
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.
answered Jul 14 at 20:35
Stanislav Bashkyrtsev
1012
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 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 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 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 at 21:53
add a comment |Â
up vote
0
down vote
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_11q_1 $$
$$a_2 = r_12q_1 + r_22q_2 $$
$$a_3 = r_13q_1 + r_23q_2 + r_33q_3$$
$$vdots $$
$$a_n = r_1nq_1 + r_2nq_n + cdots + r_nnq_n $$
$$A = tildeQtildeR $$
for when $ mgeq 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 = beginbmatrix r_11 & r_12 & cdots & r_1n \ & r_22 & & vdots \ & & ddots \ & & & r_nn endbmatrix $$
Back sub works by going to the diagonal and working backwards. If $m<n$ in the $QR$ you have more entries I believe.
answered Jul 16 at 1:02
RHowe
1,025815
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 at 6:10
The computer uses the QR decomp when it isn't square. math.stackexchange.com/questions/2836110/…
– RHowe
Jul 16 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 ofusolvefor non-square matrices!
– mike239x
Jul 16 at 15:56
@mike239x the $R$ matrix is a square matrix. Please see trefethan. Only the Q matrix may be non-square.
– RHowe
Jul 16 at 16:03
Welp, either wikipedia is wrong, or you are. $Q$ is the orthogonal matrix, and hence also square-shaped.
– mike239x
Jul 16 at 16:09
 |Â
show 3 more comments
3 Answers
3
active
oldest
votes
3 Answers
3
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
1
down vote
accepted
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.
answered Jul 18 at 21:00
egreg
164k1180187
add a comment |Â
up vote
1
down vote
accepted
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.
answered Jul 18 at 21:00
egreg
164k1180187
add a comment |Â
up vote
1
down vote
accepted
up vote
1
down vote
accepted
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.
answered Jul 18 at 21:00
egreg
164k1180187
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.
answered Jul 18 at 21:00
egreg
164k1180187
answered Jul 18 at 21:00
egreg
164k1180187
answered Jul 18 at 21:00
egreg
164k1180187
answered Jul 18 at 21:00
egreg
164k1180187
164k1180187
add a comment |Â
add a comment |Â
up vote
0
down vote
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.
answered Jul 14 at 20:35
Stanislav Bashkyrtsev
1012
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 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 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 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 at 21:53
add a comment |Â
up vote
0
down vote
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.
answered Jul 14 at 20:35
Stanislav Bashkyrtsev
1012
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 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 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 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 at 21:53
add a comment |Â
up vote
0
down vote
up vote
0
down vote
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.
answered Jul 14 at 20:35
Stanislav Bashkyrtsev
1012
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.
answered Jul 14 at 20:35
Stanislav Bashkyrtsev
1012
answered Jul 14 at 20:35
Stanislav Bashkyrtsev
1012
answered Jul 14 at 20:35
Stanislav Bashkyrtsev
1012
answered Jul 14 at 20:35
Stanislav Bashkyrtsev
1012
1012
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 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 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 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 at 21:53
add a comment |Â
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 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 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 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 at 21:53
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 at 16:35
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 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 at 16:38
It is even more weird because for the square matrices a priori it is not guaranteed there is exactly one solution...
– mike239x
Jul 15 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 at 17:37
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 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 at 21:53
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 at 21:53
add a comment |Â
up vote
0
down vote
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_11q_1 $$
$$a_2 = r_12q_1 + r_22q_2 $$
$$a_3 = r_13q_1 + r_23q_2 + r_33q_3$$
$$vdots $$
$$a_n = r_1nq_1 + r_2nq_n + cdots + r_nnq_n $$
$$A = tildeQtildeR $$
for when $ mgeq 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 = beginbmatrix r_11 & r_12 & cdots & r_1n \ & r_22 & & vdots \ & & ddots \ & & & r_nn endbmatrix $$
Back sub works by going to the diagonal and working backwards. If $m<n$ in the $QR$ you have more entries I believe.
answered Jul 16 at 1:02
RHowe
1,025815
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 at 6:10
The computer uses the QR decomp when it isn't square. math.stackexchange.com/questions/2836110/…
– RHowe
Jul 16 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 ofusolvefor non-square matrices!
– mike239x
Jul 16 at 15:56
@mike239x the $R$ matrix is a square matrix. Please see trefethan. Only the Q matrix may be non-square.
– RHowe
Jul 16 at 16:03
Welp, either wikipedia is wrong, or you are. $Q$ is the orthogonal matrix, and hence also square-shaped.
– mike239x
Jul 16 at 16:09
 |Â
show 3 more comments
up vote
0
down vote
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_11q_1 $$
$$a_2 = r_12q_1 + r_22q_2 $$
$$a_3 = r_13q_1 + r_23q_2 + r_33q_3$$
$$vdots $$
$$a_n = r_1nq_1 + r_2nq_n + cdots + r_nnq_n $$
$$A = tildeQtildeR $$
for when $ mgeq 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 = beginbmatrix r_11 & r_12 & cdots & r_1n \ & r_22 & & vdots \ & & ddots \ & & & r_nn endbmatrix $$
Back sub works by going to the diagonal and working backwards. If $m<n$ in the $QR$ you have more entries I believe.
answered Jul 16 at 1:02
RHowe
1,025815
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 at 6:10
The computer uses the QR decomp when it isn't square. math.stackexchange.com/questions/2836110/…
– RHowe
Jul 16 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 ofusolvefor non-square matrices!
– mike239x
Jul 16 at 15:56
@mike239x the $R$ matrix is a square matrix. Please see trefethan. Only the Q matrix may be non-square.
– RHowe
Jul 16 at 16:03
Welp, either wikipedia is wrong, or you are. $Q$ is the orthogonal matrix, and hence also square-shaped.
– mike239x
Jul 16 at 16:09
 |Â
show 3 more comments
up vote
0
down vote
up vote
0
down vote
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_11q_1 $$
$$a_2 = r_12q_1 + r_22q_2 $$
$$a_3 = r_13q_1 + r_23q_2 + r_33q_3$$
$$vdots $$
$$a_n = r_1nq_1 + r_2nq_n + cdots + r_nnq_n $$
$$A = tildeQtildeR $$
for when $ mgeq 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 = beginbmatrix r_11 & r_12 & cdots & r_1n \ & r_22 & & vdots \ & & ddots \ & & & r_nn endbmatrix $$
Back sub works by going to the diagonal and working backwards. If $m<n$ in the $QR$ you have more entries I believe.
answered Jul 16 at 1:02
RHowe
1,025815
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_11q_1 $$
$$a_2 = r_12q_1 + r_22q_2 $$
$$a_3 = r_13q_1 + r_23q_2 + r_33q_3$$
$$vdots $$
$$a_n = r_1nq_1 + r_2nq_n + cdots + r_nnq_n $$
$$A = tildeQtildeR $$
for when $ mgeq 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 = beginbmatrix r_11 & r_12 & cdots & r_1n \ & r_22 & & vdots \ & & ddots \ & & & r_nn endbmatrix $$
Back sub works by going to the diagonal and working backwards. If $m<n$ in the $QR$ you have more entries I believe.
answered Jul 16 at 1:02
RHowe
1,025815
edited Jul 17 at 15:07
answered Jul 16 at 1:02
RHowe
1,025815
answered Jul 16 at 1:02
RHowe
1,025815
answered Jul 16 at 1:02
RHowe
1,025815
1,025815
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 at 6:10
The computer uses the QR decomp when it isn't square. math.stackexchange.com/questions/2836110/…
– RHowe
Jul 16 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 ofusolvefor non-square matrices!
– mike239x
Jul 16 at 15:56
@mike239x the $R$ matrix is a square matrix. Please see trefethan. Only the Q matrix may be non-square.
– RHowe
Jul 16 at 16:03
Welp, either wikipedia is wrong, or you are. $Q$ is the orthogonal matrix, and hence also square-shaped.
– mike239x
Jul 16 at 16:09
 |Â
show 3 more comments
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 at 6:10
The computer uses the QR decomp when it isn't square. math.stackexchange.com/questions/2836110/…
– RHowe
Jul 16 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 ofusolvefor non-square matrices!
– mike239x
Jul 16 at 15:56
@mike239x the $R$ matrix is a square matrix. Please see trefethan. Only the Q matrix may be non-square.
– RHowe
Jul 16 at 16:03
Welp, either wikipedia is wrong, or you are. $Q$ is the orthogonal matrix, and hence also square-shaped.
– mike239x
Jul 16 at 16:09
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 at 6:10
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 at 6:10
The computer uses the QR decomp when it isn't square. math.stackexchange.com/questions/2836110/…
– RHowe
Jul 16 at 14:31
The computer uses the QR decomp when it isn't square. math.stackexchange.com/questions/2836110/…
– RHowe
Jul 16 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 at 15:56
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 at 15:56
@mike239x the $R$ matrix is a square matrix. Please see trefethan. Only the Q matrix may be non-square.
– RHowe
Jul 16 at 16:03
@mike239x the $R$ matrix is a square matrix. Please see trefethan. Only the Q matrix may be non-square.
– RHowe
Jul 16 at 16:03
Welp, either wikipedia is wrong, or you are. $Q$ is the orthogonal matrix, and hence also square-shaped.
– mike239x
Jul 16 at 16:09
Welp, either wikipedia is wrong, or you are. $Q$ is the orthogonal matrix, and hence also square-shaped.
– mike239x
Jul 16 at 16:09
 |Â
show 3 more comments
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2851699%2fsolving-u-cdot-x-b-with-triangular-matrix-u-why-should-u-be-a-square%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
MathJax works in the title, don't you know?
– Shaun
Jul 14 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 at 16:06
1
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 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 at 16:46
1
Typically matrices are not square; on the other hand, a triangular matrix is square by definition.
– egreg
Jul 17 at 15:10