Questions tagged [linear-algebra]

For challenges involving linear algebra, the mathematics of vector spaces and linear mappings between them.

Filter by
Sorted by
Tagged with
5 votes
1 answer
373 views

NxM List Combination Closest to Target

Given a list of N lists, each containing M positive integers, and a separate list of M positive integers (target values), return a list of N scalars (integers with a value of 0 or more) that ...
user avatar
  • 757
2 votes
3 answers
266 views

Appease the Picky Eater

Your friend Jack is a picky eater. He only likes certain foods, and he only likes to eat a certain amount of them each day. Despite this, Jack has very strict calorie and macronutrient goals that he ...
user avatar
  • 757
15 votes
7 answers
735 views

Are these the basis vectors?

A basis of a vector space \$V\$ is a set of vectors \$B\$ such that every vector \$\vec v \in V\$ can be uniquely written as a linear combination of the vectors in \$B\$. In other words, let \$B = \{\...
user avatar
21 votes
10 answers
2k views

Is this a Jordan matrix?

Background A Jordan matrix is a block-diagonal matrix where each block on the diagonal has the structure of $$ \begin{bmatrix} \lambda & 1 & 0 & \cdots & 0 \\ 0 &...
user avatar
  • 62.1k
14 votes
4 answers
513 views

Bad matrix multiplication that gives the right answer

Executive summary: Print NxN matrices \$A\$ and \$B\$ where \$ AB = 10A + B \$. Largest N wins! Details: Entrants in this challenge should choose an N. Submit a program that takes an input integer '...
user avatar
14 votes
5 answers
973 views

What is the Subspace Dimension?

Challenge Given the Cartesian coordinates of two or more distinct points in Euclidean n-space (\$\mathbb{R}^n\$), output the minimum dimension of a flat (affine) subspace that contains those points, ...
user avatar
  • 15.8k
17 votes
10 answers
612 views

Decomposition of a matrix in \$ SL_2(\mathbb{Z}) \$

Background The special linear group \$ SL_2(\mathbb{Z}) \$ is a multiplicative group of \$ 2 \times 2 \$ matrices whose elements are integers and determinant is 1. It is known that every member of \$...
user avatar
  • 62.1k
16 votes
14 answers
679 views

Linear dependences over the field with two elements

The \$d\$-dimensional vector space \$\mathbb{F}_2^d\$ over the field with two elements \$\mathbb{F}_2\$ is the set of vectors of \$d\$ bits. Addition of vectors is bitwise xor. A linear dependence is ...
user avatar
  • 2,075
6 votes
6 answers
426 views

Explore a Klarner-Rado sequence [duplicate]

One of the Klarner-Rado sequences is defined as follows: the first term is \$1\$ for all subsequent terms, the following rule applies: if \$x\$ is present, so are \$2x+1\$ and \$3x+1\$ the sequence ...
user avatar
  • 173
21 votes
20 answers
2k views

Reorder a matrix, twice

You are given a square \$n \times n\$ matrix \$A\$, and a list (or vector) \$u\$ of length \$n\$ containing the numbers \$1\$ through \$n\$ (or \$0\$ through \$n-1\$). Your task is to reorder the ...
user avatar
  • 9,336
29 votes
8 answers
5k views

Billiard balls collision

Given the 2-dimensional positions and velocities of a pair of billiard balls right before impact, calculate their velocities after a perfectly elastic collision. The balls are assumed to be ideal ...
user avatar
  • 14.5k
16 votes
1 answer
378 views

Decompose Commutators

A theorem in this paper1 states that every integral n-by-n matrix M over the integers with trace M = 0 is a commutator, that means there are two integral matrices A,B of the same size as M such that M ...
user avatar
  • 42.9k
24 votes
16 answers
4k views

Find the inverse of a 3 by 3 matrix

Challenge Given nine numbers, a, b, c, d, e, f, g, h, i, as input which correspond to the square matrix: $$\mathbf{M} = \begin{pmatrix}a& b& c\\ d& e&...
user avatar
  • 22.7k
-3 votes
1 answer
193 views

Print the positive non-zero integer n-tuple(s) that solve an inequality within a bound

Suppose I have a linear inequality like x0A0 + x1A1 + ... + xnAn <= C with xi a non-zero positive integer and Ai and C a positive non-zero multiple of 0.01. ...
user avatar
12 votes
7 answers
2k views

Calculate the Hafnian as quickly as possible

The challenge is to write the fastest code possible for computing the Hafnian of a matrix. The Hafnian of a symmetric 2n-by-2n ...
user avatar
24 votes
16 answers
3k views

Codegolf the Hafnian

The challenge is to write codegolf for the Hafnian of a matrix. The Hafnian of an 2n-by-2n symmetric matrix ...
user avatar
31 votes
10 answers
1k views

Find the dot product of Rationals

I was at a friend's house for dinner and they suggested the idea of a "Prime-factor vector space". In this space the positive integers are expressed as a vector such that the nth element in the ...
user avatar
  • 84.3k
23 votes
28 answers
2k views

Generalized matrix trace

Inspiration. Given (by any means): A two-argument (or single argument consisting of a two-element list) black box function, f: ℤ+ × ℤ+ → ℤ+ (input and output are 1,...
user avatar
  • 27.1k
13 votes
9 answers
2k views

Characteristic polynomial

The characteristic polynomial of a square matrix \$A\$ is defined as the polynomial \$p_A(x) = \det(Ix-A)\$ where \$I\$ is the identity matrix and \$\det\$ the determinant. Note that this definition ...
user avatar
  • 16.3k
11 votes
8 answers
2k views

Eigenvalues of a Matrix

Given a square matrix, output the matrix's eigenvalues. Each eigenvalue should be repeated a number of times equal to its algebraic multiplicity. The eigenvalues of a matrix ...
user avatar
11 votes
4 answers
606 views

Solve a matrix equation by Jacobi's method (Revised)

Mathematical Background Let A be an N by N matrix of real numbers, b a vector of N real numbers and x a vector N unknown real numbers. A matrix equation is Ax = b. Jacobi's method is as follows: ...
user avatar
34 votes
38 answers
4k views

Determinant of an Integer Matrix

Given a square integer matrix as input, output the determinant of the matrix. Rules You may assume that all elements in the matrix, the determinant of the matrix, and the total number of elements in ...
user avatar
22 votes
13 answers
2k views

Is the matrix rank-one?

Given a matrix of integers, test if it's rank-one, meaning that every row is a multiple of the same vector. For example, in ...
user avatar
  • 137k
21 votes
16 answers
2k views

Verify Eigenpairs

In this challenge, you will be given a square matrix A, a vector v, and a scalar λ. You will ...
user avatar
  • 40.1k
27 votes
10 answers
4k views

Symbolic matrix multiplication

There are lots of different ways to explain matrix multiplication. I'll stick with a single figure since I believe most people here are familiar with it (and the figure is very descriptive). If you ...
user avatar
21 votes
8 answers
3k views

Arnold's Cat Map

Challenge Given a colour raster image* with the same width and height, output the image transformed under Arnold's cat map. (*details see below) Definition Given the size of the image ...
user avatar
  • 42.9k
15 votes
3 answers
444 views

Totally Invertible Submatrices

(inspired by this question over on Math) The Definitions Given an n x n square matrix A, we can call it invertible if there ...
user avatar
  • 42.8k
14 votes
7 answers
400 views

Generate binary matrices which are distinct up to reflections

Here are all the 2x2 binary matrices ...
user avatar
  • 891
10 votes
13 answers
676 views

Dot Product of Diagonals

This challenge is very simple. You are given as input a square matrix, represented in any sane way, and you have to output the dot product of the diagonals of the matrix. The diagonals in specific are ...
user avatar
  • 25.5k
17 votes
3 answers
333 views

Self Referential Polynomials

For every given degree \$n\$ it is possible to construct (at least one) an integral polynomial \$p \in \mathbb Z[X]\$ such that \$p(k)\$ (\$p\$ evaluated in \$k\$) is the coefficient of the term \$x^k\...
user avatar
  • 42.9k
18 votes
5 answers
1k views

Jordan Decomposition

Important note: Because this challenge only applies to square matrices, any time I use the term "matrix", it is assumed that I am referring to a square matrix. I am leaving off the "...
user avatar
15 votes
8 answers
3k views

Matrix Trigonometry

Introduction The two most common trigonometric functions, sine and cosine (or sin and ...
user avatar
13 votes
9 answers
2k views

Calculate the Kronecker Product

Related, but very different. In the examples below, \$A\$ and \$B\$ will be \$2\times2\$ matrices, and the matrices are one-indexed. A Kronecker product has the following properties: ...
user avatar
11 votes
15 answers
1k views

Find the Matrix Power

Problem Create a program or function that can calculate the result of a matrix raised to the nth power. Your code will take an arbitrary square matrix A and a non-negative integer n, and return a ...
user avatar
  • 16.4k
9 votes
6 answers
1k views

Calculate the Kronecker sum of two matrices

In the examples below, A and B will be 2-by-2 matrices, and the matrices are one-indexed. A Kronecker product has the ...
user avatar
4 votes
13 answers
1k views

Linear Independence

Given a set of vectors all of the same positive finite dimension, output a falsey value if they are linearly dependent and a truthy value if they are linearly independent. A set of vectors v1, v2, ... ...
user avatar
  • 1,293
11 votes
4 answers
1k views

Solve a Linear Equation

This challenge but with a better spec. Spec Your program will take a linear equation containing a single variable x and output the value of ...
user avatar
  • 28.4k
26 votes
24 answers
1k views

Vandermonde Determinant

Given a vector of \$n\$ values \$(x_1,x_2,x_3,\ldots,x_n)\$ return the determinant of the corresponding Vandermonde matrix \$V(x_1, x_2, \ldots, x_n) = \begin{bmatrix}1 & x_1 & x_1^2 & x_1^...
user avatar
  • 42.9k
18 votes
12 answers
1k views

Recursive 2x2 determinant

The determinant of a 2 by 2 matrix a b c d is given by ad - bc. Given a matrix of digits with dimensions 2n by 2n, n ≥ 1, ...
user avatar
  • 60.9k
21 votes
20 answers
2k views

Find the Cross Product

The cross product of two three-dimensional vectors \$\vec a\$ and \$\vec b\$ is the unique vector \$\vec c\$ such that: \$\vec c\$ is orthogonal to both \$\vec a\$ and \$\vec b\$ The magnitude of \$...
user avatar
  • 21.2k
44 votes
85 answers
5k views

Construct the Identity Matrix

The challenge is very simple. Given an integer input n, output the n x n identity matrix. The identity matrix is one that has <...
user avatar
  • 1,297
19 votes
6 answers
1k views

Cofactor Matrices

The cofactor matrix is the transpose of the Adjugate Matrix. The elements of this matrix are the cofactors of the original matrix. The cofactor (i.e. the element of the cofactor matrix at row i and ...
user avatar
  • 35.2k
14 votes
12 answers
1k views

Construct a companion matrix

You have a number of polynomials who are lonely, so make them some companions (who won’t threaten to stab)! For a polynomial of degree n, there is an ...
user avatar
  • 1,035
9 votes
1 answer
2k views

Reduced Row-Echelon Form of a Matrix

The goal of this challenge is to create a program that takes in a matrix and outputs its reduced row-echelon form. A matrix is in reduced row-echelon form if it meets all of the following ...
user avatar
  • 7,406
12 votes
4 answers
612 views

Multiply Pauli Matrices

The Pauli matrices are a set of 2x2 matrices which appear very commonly in quantum physics (no, you don't need to know any quantum physics for this challenge). If we include the identity in the set, ...
user avatar
-3 votes
1 answer
517 views

Find the inverse of a matrix

Write a full program to calculate the inverse of a 4-by-4 matrix. Rules The sixteen values of the initial matrix must be hard-coded to variables, as follows: ...
user avatar
  • 10.8k
15 votes
4 answers
1k views

Solve a 2x2 Eigensystem

For those with a little linear algebra background, the challenge is as simple as this: determine the eigenvalues and eigenvectors of a given complex 2x2 matrix. You may skip ahead to The Challenge for ...
user avatar