Questions tagged [linear-algebra]
For challenges involving linear algebra, the mathematics of vector spaces and linear mappings between them.
51
questions
24
votes
37
answers
2k
views
Diagonalize a vector
Diagonalize a vector into a matrix.
Input
A vector, list, array, etc. of integers \$\mathbf{v}\$ of length \$n\$.
Output
A \$n \times n\$ matrix, 2D array, etc. \$A\$ such that for each element \$a_i \...
- 8,258
1
vote
0
answers
109
views
Print all semimagic squares [closed]
I am working on a code to print all semimagic squares [1] of a given size. I am working with the following definition:
An \$n\times n\$ consists of numbers \$1,2,\cdots, n^2\$.
All numbers must be ...
- 111
15
votes
13
answers
1k
views
Hankel transform of an integer sequence
A Hankel matrix is a square matrix in which each ascending skew-diagonal from left to right is constant, e.g.:
$$\begin{bmatrix} a & b & c & d \\ b & c & d & e \\ c & d &...
- 45.6k
7
votes
0
answers
203
views
Find the linear transformation
Given a set of bit vectors \$A\$ and a binary matrix \$M\$, we can define the set \$MA = \{ Mx : x \in A \}\$, where \$ M x \$ is the result of the matrix multiplication of \$ M \$ by \$ x \$ over \$\...
- 7,517
7
votes
2
answers
474
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 ...
- 747
3
votes
3
answers
328
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 ...
- 747
15
votes
7
answers
756
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 = \{\...
- 49.3k
21
votes
11
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 &...
- 73.2k
14
votes
4
answers
639
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 '...
- 1,111
14
votes
5
answers
979
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, ...
- 16.2k
17
votes
10
answers
695
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 \$...
- 73.2k
16
votes
14
answers
689
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 ...
- 2,085
6
votes
6
answers
540
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 ...
- 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 ...
- 9,446
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 ...
- 15.2k
16
votes
1
answer
395
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 ...
- 43.6k
24
votes
18
answers
5k
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&...
- 23.2k
-3
votes
1
answer
195
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. ...
12
votes
9
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 ...
user9206
25
votes
17
answers
3k
views
Codegolf the Hafnian
The challenge is to write codegolf for the Hafnian of a matrix.
The Hafnian of an \$2n \times 2n\$ symmetric matrix \$A\$ is defined as:
$$\operatorname{haf}(A) = \frac 1 {n!2^n} \sum_{\sigma \in S_{...
user9206
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 ...
- 95.5k
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,...
- 29.8k
14
votes
13
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 ...
- 16.7k
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 ...
user45941
11
votes
4
answers
689
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: ...
- 219
37
votes
39
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 ...
user45941
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
...
- 144k
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 ...
- 41.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 ...
- 46.1k
21
votes
8
answers
4k
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 ...
- 43.6k
15
votes
3
answers
455
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 ...
- 43.3k
14
votes
7
answers
408
views
Generate binary matrices which are distinct up to reflections
Here are all the 2x2 binary matrices
...
- 891
10
votes
13
answers
723
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 ...
- 25.7k
19
votes
4
answers
376
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\...
- 43.6k
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 "...
user45941
15
votes
9
answers
4k
views
Matrix Trigonometry
Introduction
The two most common trigonometric functions, sine and cosine (or sin and ...
user45941
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:
...
- 46.1k
11
votes
15
answers
2k
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 ...
- 16.8k
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 ...
- 46.1k
5
votes
13
answers
2k
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, ... ...
- 1,303
13
votes
6
answers
2k
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 ...
- 28.9k
29
votes
26
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^...
- 43.6k
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, ...
- 61.7k
23
votes
22
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 \$...
- 21.4k
48
votes
105
answers
6k
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 <...
- 1,377
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 ...
- 38.3k
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 ...
- 1,035
10
votes
2
answers
3k
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 ...
- 7,502
12
votes
4
answers
679
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, ...
- 196k
-3
votes
1
answer
539
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:
...
- 10.8k