16
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ Comments are not for extended discussion; this conversation has been moved to chat. \$\endgroup\$ – Dennis Dec 28 '17 at 0:12
5
\$\begingroup\$

Julia, 2 bytes

qr

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

Try it online!

\$\endgroup\$
  • 4
    \$\begingroup\$ Nice to see you! It doesn't get any shorter than this :-) \$\endgroup\$ – Luis Mendo Dec 27 '17 at 1:15
  • \$\begingroup\$ I knew you would come back shortly. Welcome back! What a built-in BTW... \$\endgroup\$ – Erik the Outgolfer Dec 27 '17 at 5:59
5
\$\begingroup\$

Octave, 19 bytes

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

Try it online!

My first Octave answer \o/

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)...

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

Wolfram Language (Mathematica), 15 bytes

QRDecomposition

Try it online!

I mean... what can I say?

\$\endgroup\$
3
\$\begingroup\$

R, 38 37 bytes

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

Try it online!

\$\endgroup\$
  • 1
    \$\begingroup\$ You don’t need that space...? pryr::f(list(qr.R(q<-qr(m)),qr.R(q))) \$\endgroup\$ – Mr. Xcoder Dec 26 '17 at 22:02
  • 1
    \$\begingroup\$ Does it work on all-zero matrices? \$\endgroup\$ – Adám Dec 26 '17 at 22:57
  • \$\begingroup\$ @Mr.Xcoder Thanks! \$\endgroup\$ – rturnbull Dec 27 '17 at 1:18
  • \$\begingroup\$ @Adám Thanks, I had made a stupid typo. Fixed now. \$\endgroup\$ – rturnbull Dec 27 '17 at 1:18
1
\$\begingroup\$

SageMath, 27 bytes

lambda x:matrix(RDF,x).QR()
\$\endgroup\$
1
\$\begingroup\$

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
\$\endgroup\$
  • 2
    \$\begingroup\$ 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. \$\endgroup\$ – Wheat Wizard Dec 27 '17 at 1:27
  • \$\begingroup\$ @WheatWizard Thanks :) \$\endgroup\$ – Tyilo Dec 27 '17 at 3:24
  • 1
    \$\begingroup\$ Unfortunately, this won't work for matrices with null rows. \$\endgroup\$ – Dennis Dec 27 '17 at 14:22
0
\$\begingroup\$

Python with numpy, 28 bytes

import numpy
numpy.linalg.qr
\$\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.