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

7 Answers 7

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\$
2
  • 4
    \$\begingroup\$ Nice to see you! It doesn't get any shorter than this :-) \$\endgroup\$
    – Luis Mendo
    Commented Dec 27, 2017 at 1:15
  • \$\begingroup\$ I knew you would come back shortly. Welcome back! What a built-in BTW... \$\endgroup\$ Commented Dec 27, 2017 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\$
6
  • \$\begingroup\$ So… will you post that J solution or shall I? \$\endgroup\$
    – Adám
    Commented Dec 26, 2017 at 22:27
  • \$\begingroup\$ @Adám I won’t. Go ahead and post it if you want. \$\endgroup\$
    – Mr. Xcoder
    Commented Dec 26, 2017 at 22:27
  • \$\begingroup\$ Why doesn't 128!:0 work on an all-zero matrix‽ \$\endgroup\$
    – Adám
    Commented Dec 26, 2017 at 22:31
  • 2
    \$\begingroup\$ Does it work on all-zero matrices? \$\endgroup\$
    – Adám
    Commented Dec 26, 2017 at 22:58
  • \$\begingroup\$ @LuisMendo Thanks a lot for the fix! \$\endgroup\$
    – Mr. Xcoder
    Commented Dec 27, 2017 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\$
3
  • 1
    \$\begingroup\$ You don’t need that space...? pryr::f(list(qr.R(q<-qr(m)),qr.R(q))) \$\endgroup\$
    – Mr. Xcoder
    Commented Dec 26, 2017 at 22:02
  • 1
    \$\begingroup\$ Does it work on all-zero matrices? \$\endgroup\$
    – Adám
    Commented Dec 26, 2017 at 22:57
  • \$\begingroup\$ @Adám Thanks, I had made a stupid typo. Fixed now. \$\endgroup\$
    – rturnbull
    Commented Dec 27, 2017 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\$
3
  • 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
    Commented Dec 27, 2017 at 1:27
  • \$\begingroup\$ @WheatWizard Thanks :) \$\endgroup\$
    – Tyilo
    Commented Dec 27, 2017 at 3:24
  • 1
    \$\begingroup\$ Unfortunately, this won't work for matrices with null rows. \$\endgroup\$
    – Dennis
    Commented Dec 27, 2017 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 and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.