Queue Our Decomposition

In this challenge I will ask you to find a QR decomposition of a square matrix. The QR decomposition of matrix A is two Matrices Q and R such that A = QR. In particular we are looking for Q to be an orthogonal matrix (that is QTQ=QQT=I where I is the multiplicative identity and T is the transpose) and R to be a upper triangular matrix (every value below its diagonal must be zero).

You will write code that takes a square matrix by any reasonable method and outputs a QR decomposition by any method. Many matrices have multiple QR decompositions however you only ever need output one.

Elements of your resultant matrices should be within two decimal places of an actual answer for every entry in the matrix.

This is a competition so answers will be scored in bytes with fewer bytes being a better score.

Test Cases

These are only possible outputs, your outputs need not match all of these as long as they are valid.

0 0 0     1 0 0   0 0 0
0 0 0 ->  0 1 0   0 0 0
0 0 0     0 0 1 , 0 0 0

1 0 0     1 0 0   1 0 0
0 1 0 ->  0 1 0   0 1 0
0 0 1     0 0 1 , 0 0 1

1 2 3     1 0 0   1 2 3
0 3 1 ->  0 1 0   0 3 1
0 0 8     0 0 1 , 0 0 8

0 0 1     0 0 1   1 1 1
0 1 0 ->  0 1 0   0 1 0
1 1 1     1 0 0 , 0 0 1

0 0 0 0 1     0 0 0 0 1   1 0 0 0 1
0 0 0 1 0     0 0 0 1 0   0 1 1 1 0
0 0 1 0 0 ->  0 0 1 0 0   0 0 1 0 0
0 1 1 1 0     0 1 0 0 0   0 0 0 1 0
1 0 0 0 1     1 0 0 0 0 , 0 0 0 0 1

• Comments are not for extended discussion; this conversation has been moved to chat. Commented Dec 28, 2017 at 0:12

Julia, 2 bytes

qr


The function qr accepts a square matrix and returns a Tuple of matrices: Q and R.

Try it online!

• Nice to see you! It doesn't get any shorter than this :-) Commented Dec 27, 2017 at 1:15
• I knew you would come back shortly. Welcome back! What a built-in BTW... Commented Dec 27, 2017 at 5:59

Octave, 19 bytes

@(x)[[q,r]=qr(x),r]


Try it online!

Octave’s qr has quite a few alternatives in other languages that return both Q and R: QRDecomposition (Mathematica), matqr (PARI/GP), 128!:0 - if I recall correctly - (J), qr (R)...

• So… will you post that J solution or shall I?
Commented Dec 26, 2017 at 22:27
• @Adám I won’t. Go ahead and post it if you want. Commented Dec 26, 2017 at 22:27
• Why doesn't 128!:0 work on an all-zero matrix‽
Commented Dec 26, 2017 at 22:31
• Does it work on all-zero matrices?
Commented Dec 26, 2017 at 22:58
• @LuisMendo Thanks a lot for the fix! Commented Dec 27, 2017 at 6:38

Wolfram Language (Mathematica), 15 bytes

QRDecomposition


Try it online!

I mean... what can I say?

R, 38 37 bytes

pryr::f(list(qr.R(q<-qr(m)),qr.Q(q)))


Try it online!

• You don’t need that space...? pryr::f(list(qr.R(q<-qr(m)),qr.R(q))) Commented Dec 26, 2017 at 22:02
• Does it work on all-zero matrices?
Commented Dec 26, 2017 at 22:57
• @Adám Thanks, I had made a stupid typo. Fixed now. Commented Dec 27, 2017 at 1:18

SageMath, 27 bytes

lambda x:matrix(RDF,x).QR()


Python 2, 329 324 bytes

import fractions
I=lambda v,w:sum(a*b for a,b in zip(v,w))
def f(A):
A,U=[map(fractions.Fraction,x)for x in zip(*A)],[]
for a in A:
u=a
for v in U:u=[x-y*I(v,a)/I(v,v)for x,y in zip(u,v)]
U.append(u)
Q=[[a/I(u,u)**.5 for a in u]for u in U];return zip(*Q),[[I(e,a)*(i>=j)for i,a in enumerate(A)]for j,e in enumerate(Q)]


We must use fractions to ensure correct output, see https://en.wikipedia.org/wiki/Gram%E2%80%93Schmidt_process#Numerical_stability

Indentation used:

1. 1 space
2. 1 tab
• When indented you can save bytes by using ; to separate lines. You can also often forgo the line break after :. I would suggest playing around with these because I can see a few places this answer can be shorter using this technique. Commented Dec 27, 2017 at 1:27
• @WheatWizard Thanks :) Commented Dec 27, 2017 at 3:24
• Unfortunately, this won't work for matrices with null rows. Commented Dec 27, 2017 at 14:22

Python with numpy, 28 bytes

import numpy
numpy.linalg.qr