# Questions tagged [linear-algebra]

The tag has no usage guidance.

262 questions
Filter by
Sorted by
Tagged with
1 vote
29 views

Suppose I have a reduced row echelon form of a matrix for linear equations. The pivots from the corresponding Gaussian elimination are available. For example, in $$\begin{pmatrix} 1 & 0 & 0 \\... 2 votes 1 answer 38 views ### Straight forward algorithm for obtaining a sub matrix Ok so I just started writing a linear algebra toolbox in C++ for some other projects I have / plan on starting in the future. So I define a matrix as the fundamental building block and vectors, ... • 21 1 vote 0 answers 21 views ### Find a basis of a vector space minimizing the numbers of nonzero coordinates for a bunch of vectors I've got a (to be a bit specific) 84-dimensional rational vector space, and as many as 1197 vectors in it. In the basis of the space that I've got, numbers of nonzero coordinates for these vectors ... 1 vote 0 answers 15 views ### Effect of using signed vectors for LSH Random Projection (Simhash) Simhash is an text similarity algorithm proposed by Moses Charikar in his paper "Similarity Estimation Techniques from Rounding Algorithms". However, in his original paper, he proposed to ... • 111 0 votes 0 answers 27 views ### Kronecker Decomposition Algorithm I am looking for an algorithm that decomposes a 2^n square matrix into a Kronecker product \otimes of n number of 2 \times 2 matrices. Does anyone know if there is an implementation out there ... 0 votes 1 answer 29 views ### Fit data to a lookup table I have been looking for methods to fit 1-D data to a lookup table. In other words, there's no known function that is used as a model. For example in the plots below, the measured data (blue) is fit to ... 2 votes 1 answer 31 views ### Given a family of 0-1 matrices M find the sum of matrices from M which has minimal rank Given a family of matrices M with entries in \mathbb{F}_2 find the subset N \subseteq M  such that the rank of the matrix$$A = \sum_{m \in N}m $$is minimal. I am wondering if anyone have seen ... • 225 1 vote 1 answer 23 views ### Algorithm for solving linear equations if interested only in the first component If I want to solve \mathbf A \mathbf x = \mathbf b, but I am only interested in the value of x_1, what algorithm should I use, and will it always be strictly more efficient than solving for all of ... 5 votes 1 answer 63 views ### Given a set of points S which is a subset of a vector space V, find the smallest subspace which intersect S in at least k points Given a set of points S which is a subset of a vector space V I want to want the smallest subspace of A of V such that |A \cap S| \geq k . I suspect some variant of this problem would have ... • 225 3 votes 1 answer 86 views ### How does numpy.linalg.inv calculate the inverse of a matrix? What is the algorithm behind this routine and is there documentation available for it? 0 votes 1 answer 36 views ### Strange notation in the article about sparse self-attention While reading an article devoted to the sparse self-attention, I came across a notation that was not very clear:$$ Attend(X, S) = \Big( a(x_i, S_i) \Big)_{i∈{\{1,...,n}\}} $$What means \Big( \space ... 3 votes 1 answer 94 views ### Mathematical operation for removing duplicate rows in a matrix I am using the GraphBLAS C API (https://graphblas.org/) which provides an interface for performing mathematical operations on sparse matrices. Given an adjacency matrix \mathbf{A}: \mathbb{R}^{n \... 0 votes 1 answer 40 views ### Finding solution to Mv=v over \mathbb{Z}={0,1} for matrix M given a set linearly independent v Under mod 2 arithmetic (\mathbb{Z}={0,1}), given a set V of nx1 linearly independent vectors \{x_1,...,x_n\} I'd like to find a n^2 binary matrix M such that Mv=v where v \in V and ... • 404 2 votes 1 answer 79 views ### Efficient algorithm for finding a vector to maximize the number of positive dot products with a given set (finding the maximum overlap of half-spaces) I have a large set \mathbf{V} of vectors in \mathbb{R}^d\setminus\{\mathbf{0}\} and need to find a vector \mathbf{u} that maximizes \sum_{\mathbf{v}\in\mathbf{V}}\mathbf{1}_{\mathbf{u}\cdot\... 0 votes 0 answers 36 views ### Modify this GEPP algorithm to work with matrices I've been stuck with this problem for a day or so, and I really can't figure it out. I need to modify this pseudocode so that it works when b is not just a vector, but a matrix with same number of ... 0 votes 2 answers 105 views ### Can any SAT problem be converted to a system of linear equations over \mathbf{Z}_2? Can any SAT problem be converted into one with only affine formulas? Handbook of Satisfiability p. 672: Affine formulas. A linear equation over the two-element field is an expression of the form x_1 ... • 154 1 vote 0 answers 16 views ### Optimal top-k column subset Let V be a set of vectors over \mathbb{R}^l, l\ge 1, \pi_i(V) be the permutation of vectors in V such that they are ordered by their ith component (descending) in order for \pi_i(V)(\... • 141 0 votes 0 answers 52 views ### Getting a V-representation from an H-Representation of a polytope I am trying to find an easy to follow resource on implementing any (reasonable) algorithm to find a V-represnetation of a polytope from its h-representation. I only need this to work for \mathbb{R}^... • 341 0 votes 0 answers 20 views ### Are there free/paid DISTRIBUTED solvers for a large system pf linear equations? I've been doings some research into distributed solutions for a large system of linear equations (reading papers such as Wang et al.'s "Solving a system of linear equations: From centralized to ... 0 votes 1 answer 59 views ### Can a linear programming method be used to solve systems of inequalities with OR (disparate) compound inequalities? I recently discovered linear programming and it seemed perfect for a CS problem I wanted to solve a few months ago. This task involved solving a large quantity of inequalities at once. For example, ... 4 votes 2 answers 117 views ### Finding a vector of maximum Hamming distance from a subspace of (\mathbb{Z}/2\mathbb{Z})^n Let W be a linear subspace of the vector space V = (\mathbb{Z}/2\mathbb{Z})^n. Let k = \dim(W). For v \in V, define the distance from v to W to be d(v,W):=\min_{w\in W} d(v,w) where d(... • 141 1 vote 0 answers 21 views ### Algorithm for checking whether a set of hyperplanes covers \mathbb{Z}_r^n In what follows, r \in \mathbb{N} is not necessarily prime. \mathbb{Z}_r is shorthand for \mathbb{Z}/r\mathbb{Z}. Given a set of h hyperplanes A \vec x = b \mod r, we can check whether the ... • 378 3 votes 1 answer 89 views ### A version of Bareiss algorithm or similar for symmetric matrices A linear equation Ax=b can be solved by reducing the matrix A to upper triangular form by using Gaussian elimination or LU decomposition. If A is symmetric and positive definite one can use ... 1 vote 0 answers 43 views ### Algorithm for the inversion of a striped matrix with tridiagonal stripes I'd like to compute the inverse of a matrix of size S^2N \times S^2N over complex numbers that is composed of tri-diagonal S\times S size blocks of tri-diagonal S\times S block matrices. This ... • 11 5 votes 1 answer 69 views ### Find orthogonal (integer) vectors in set I have very large sets A,B of 4-tuples of integers, and I would like to find (x_1,y_1,z_1,w_1)\in A,(x_2,y_2,z_2,w_2)\in B such that$$x_1x_2 + y_1y_2 + z_1z_2 + w_1w_2 = 0.$$Of course the naive ... • 281 2 votes 0 answers 68 views ### Permuting matrix entries to lower rank Suppose I have a rank-k matrix A \in \mathbf{R}^{m \times n}. Now suppose this matrix has its elements shuffled by an adversary to maximize the rank. Is there a way to reverse this permutation and ... 0 votes 3 answers 65 views ### Linear algebra matrix coding to solve specific formula I have a formula which cannot be expressed in terms of y. ... • 103 1 vote 2 answers 605 views ### Can dot producting the result of vector-matrix multiplication speed up the runtime? Suppose we have a matrix A of dimension n \times n and two vectors \vec{u} and \vec{v} of dimension n. Then we have A\vec{v} = \vec{x} with time complexity O(n^2) and space complexity O(... • 187 1 vote 1 answer 42 views ### Efficiently finding/ sampling from all solutions to a constrained linear problem Start with N>3 vectors \vec{v}_I in \mathbb{R}^3_+, any 3 of which are linearly independent. I here ranges from 0 to N-1. Let v_{\left[abc\right]} be a matrix in \mathbb{R}^{3 \... • 113 0 votes 0 answers 56 views ### Complexity of calculating Takagi's factorization of n \times n matrix As described here the Takagi factorization of a square symmetric complex matrix A=VDV^T where D is a real nonnegative diagonal matrix, and V is unitary. I'm wondering what the complexity of ... • 53 1 vote 0 answers 24 views ### Element in linear subspace with maximum number of zeros Given a real matrix M \in \mathbb{R}^{n \times m} and a vector v \in \mathbb{R}^{n} I would like to find an element x \in \mathbb{R}^m such that v - Mx has maximum number of zeros. If the ... • 111 0 votes 1 answer 10 views ### Checking for equality before calculating product of a matrix with inverse of another matrix I have an operation that is performed many times and is thus performance sensitive where I need to calculate product of a matrix and inverse of a matrix as below. Both matrices are 4x4 and consist of ... • 177 1 vote 1 answer 80 views ### Is there a way to find the fixed size subsequence sum in an N by M array that is the closest to a given N-dimensional vector? Basically, I need to solve the multivariate case of the "closest subsequence sum to a given value K" problem, which is solved with dynamic programming as far as I understand. Let's say I ... • 13 2 votes 0 answers 42 views ### Solving Small even set problem (SES) using Shortest lattice vector problem (SVP) Suppose that you are given an algorithm A that finds the optimal solution to the shortest lattice vector problem (SVP) in time t(n) I am trying to solve the Small even set problem (SES) using it: ... • 21 1 vote 0 answers 69 views ### Estimating column sums of A_1,\ A_1 A_2,\ A_1A_2A_3,\ \ldots Given n\times n dense real valued matrices A_1,\ldots, A_L let P_i=A_1\ldots A_i For each P_i I'm interested in obtaining the sum of all rows, and the sum of all columns. Naive approach: ... 0 votes 0 answers 98 views ### Given a 2D Array (of 0's and 1's), find the minimum number of rows required so that maximum columns have their sum greater than a threshold I have a 2D array of some rows and columns which are having only 0's and 1's. I would want to know if there is a way to optimize the number of rows so that maximum number of columns have their column ... 1 vote 0 answers 38 views ### Fourier Dimension of Boolean functions I was recently reading about Fourier dimension of Boolean functions. What I understand is that if we take the Fourier expansion of f: \{\pm1\}^n \to \{\pm1\} and consider the monomials with non zero ... • 123 1 vote 2 answers 265 views ### Clarification regarding linear boolean functions! I am a little confused when it comes to linear boolean functions. According to this post: What is a simple way of explaining what a linear boolean function means in boolean algebra and relating it to ... • 13 1 vote 1 answer 326 views ### Complexity of finding d largest eigenvectors of a symmetric matrix I know that for n \times n matrix, it takes O(n^2) time complexity to compute the largest eigenpair of the matrix using Power method or etc. I'm interested to further extend the case so that now ... • 123 0 votes 1 answer 44 views ### Getting a "sub-polytope" of a concave d-dimensional polytope, given some one dimensional inequality The question will be hard to understand without an example, so let's given an example first: Let's say I have a 2 dimensional concave polytope, defined by a circular sequence of its vertices: (0,0), (... 1 vote 0 answers 211 views ### Is there an alternative method to using Gaussian elimination in order to solve 3-XORSAT I have a large system of 3-XORSAT constraints (i.e. up to 3 variables per constraint) and this can be represented in matrix form as a linear algebra problem Ax=b mod 2. Solvability (i.e. ... • 11 1 vote 1 answer 43 views ### (Approximation) Algorithms for Weight Distribution / Subspace Weights Problem in coding theory [closed] The Weight Distribution / Subspace Weights Problem in coding theory is defined as this: Instance: A binary m byn matrix H and an integer k > 0 Question: Is there a set of k columns of ... 0 votes 1 answer 118 views ### Finding a d-dimensional hyperplane containing n given points I'm currently trying to find the equation of the d-dimensional hyperplane which includes n given points, where n \ge d. Theoretically, it isn't hard - the d-dimensional hyperplane is ... 1 vote 0 answers 24 views ### Algorithmic ideas to multiply two tall & skinny matrices into one large square matrix? This problems comes from AI, and it looks something like this: I am supposed to multiply two floating-point matrices A * B. A ... 0 votes 0 answers 21 views ### Is one set of vectors constructed by another set of vectors? Let there be given set of vectors V = \{v_1, v_2, ..., v_n\} and set of vectors S = \{s_1, s_2, ..., s_k\} where n > k. The set of vectors V can be constructed by S if the vectors in V ... 0 votes 0 answers 46 views ### Which of these algorithms will involve the least amount of math? I'm taking an algorithms class for my computer science degree, and one of the requirements is to research and present 3 different algorithms. The only problem: linear algebra wasn't a prerequisite to ... 0 votes 0 answers 45 views ### Finding a set of 9 integers that minimize an error function I have an algorithm that takes a 3d triangle PMN(which is constructed from running a function that converts per-vertex UV coordinates to a PMN triangle) and P' which is a randomly chosen 3D point that ... • 101 5 votes 0 answers 103 views ### Optimization problem with discrete and continuous components Suppose we have a sequence of m tokens (T_1, T_2, \ldots, T_m). We can split this sequence considering two parameters w (which is the width of the window) and x which is the overlap between ... • 265 0 votes 0 answers 35 views ### Kalman Filter - Dynamic System Given the two equations below$$ \begin{aligned} 300x + 400y &= 700 \\ 100x + 133y &= 233 \end{aligned} how can one find a solution for those equations using Kalman filter (and suppose the ...
• 97
Let $u$ be a real vector of $m$ entries, and $A$ be a $\pm 1$ matrix of dimension $N\times m$, and real rank $\operatorname{rank}(A) = r$. What are some conditions on $A$ (e.g. in terms of its rank $r$...