Skip to main content

Questions tagged [linear-algebra]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
2 votes
1 answer
29 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 ...
Sander's user avatar
  • 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 ...
Shaikh Ammar's user avatar
5 votes
1 answer
61 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 ...
Sander's user avatar
  • 225
3 votes
1 answer
69 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?
oogabooga's user avatar
0 votes
1 answer
31 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 ...
b1ackf0x's user avatar
2 votes
1 answer
67 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 \...
codeing_monkey's user avatar
0 votes
1 answer
38 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 $n$x$1$ 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 $...
James Bowery's user avatar
2 votes
1 answer
69 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\...
multiplywithadot's user avatar
0 votes
0 answers
33 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 ...
king michael's user avatar
0 votes
2 answers
82 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 ...
Geremia's user avatar
  • 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 $i$th component (descending) in order for $\pi_i(V)(\...
Eli Bixby's user avatar
  • 141
0 votes
0 answers
40 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}^...
Makogan's user avatar
  • 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 ...
Karla's user avatar
  • 1
0 votes
0 answers
21 views

Algorithm for computing the vertices of a polytope defined as the intersection of half spaces

There's a very similarly sounding question with an answer already, but my setup is very, very different. You are given $k$ half spaces in dimension $d$, defined by a point and a direction. You want to ...
Makogan's user avatar
  • 341
0 votes
1 answer
53 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, ...
Ed_Silver's user avatar
4 votes
2 answers
111 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(...
Ben's user avatar
  • 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 ...
Jake's user avatar
  • 378
2 votes
1 answer
79 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 ...
QuantumWiz's user avatar
0 votes
0 answers
13 views

Does T5 or another embedding embed every possible length tokenization?

I’m curious about an embedding technique where every possible “tokenization” of a text gets an embedding - not just individuals words, but every single 2-gram, 3-gram, and n-gram. Does this exist? Or ...
Julius Hamilton's user avatar
1 vote
0 answers
40 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 ...
Ezrael's user avatar
  • 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 $...
pommicket's user avatar
  • 281
2 votes
0 answers
65 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 ...
Calvin Elder's user avatar
0 votes
3 answers
61 views

Linear algebra matrix coding to solve specific formula

I have a formula which cannot be expressed in terms of y. ...
Chris Degnen's user avatar
1 vote
2 answers
557 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(...
yosmo78's user avatar
  • 187
1 vote
1 answer
40 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 \...
kram1032's user avatar
  • 113
0 votes
0 answers
54 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 ...
atman's user avatar
  • 53
1 vote
0 answers
19 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 ...
Lewwwer's user avatar
  • 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 ...
Lenny White's user avatar
1 vote
1 answer
79 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 ...
oleg's user avatar
  • 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: ...
noam_y's user avatar
  • 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: ...
Yaroslav Bulatov's user avatar
0 votes
0 answers
97 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 ...
Pramod Gopinath's user avatar
1 vote
0 answers
36 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 ...
kleinbottle's user avatar
1 vote
2 answers
250 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 ...
Reppiz's user avatar
  • 13
1 vote
1 answer
271 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 ...
Jon Megan's user avatar
  • 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), (...
Ron Michal's user avatar
1 vote
0 answers
196 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. ...
scobiem's user avatar
  • 11
1 vote
1 answer
42 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$ by$n$ matrix $H$ and an integer $k > 0$ Question: Is there a set of $k$ columns of $...
borekking's user avatar
0 votes
1 answer
100 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 ...
Ron Michal's user avatar
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 ...
Azuresonance's user avatar
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$ ...
Eauriel's user avatar
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 ...
discreteboy's user avatar
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 ...
Suic's user avatar
  • 101
5 votes
0 answers
102 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 ...
dpalma's user avatar
  • 265
0 votes
0 answers
34 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 ...
Mabadai's user avatar
  • 97
3 votes
0 answers
44 views

Bound on the number of signed sums of a non-zero vector that can all equal zero

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$...
gen's user avatar
  • 991
0 votes
1 answer
94 views

can similarity transformation be linear transformation?

Learning Computer Graphics - Can similarity transformation be linear transformation? Similarity T is a rigid transformation (translation and rotations) with uniform scaling. so I guess a similarity ...
learningtocode's user avatar
2 votes
1 answer
49 views

What is this linear optimization problem?

Given a $d$-dimensional vector $v = (v_1,\dots,v_d) \in \Bbb{R}^d$, we define $f(v) = \min_{i\in [d]} \{v_i\}$ to be the smallest coordinate of $v$. Let $v^1,\dots,v^n \in \Bbb{R}^d_{\ge 0}$ be non-...
Zach Hunter's user avatar
0 votes
0 answers
26 views

How to eliminate « a priori » all vectors in a list of vectors whose scalar product with a given vector is zero without calculating the product

How to eliminate « a priori » all vectors in a list of vectors, whose scalar product with a given vector is zero, without actually calculating the product ? One solution would be to store the ...
Serge Hulne's user avatar
0 votes
0 answers
48 views

Recommendations on where to learn and practice linear programming?

[CLOSED] Thanks! I am studying Linear Programming in college but I am facing some difficulties to assimilate some concepts. So do you have any recommendations of materials to learn or practice Linear ...
Ana Carolina Gomes's user avatar

1
2 3 4 5 6