Questions tagged [linear-algebra]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
1
vote
0answers
13 views

N-dimensional generalization of map and reduce?

Is there any conceptual generalization of higher-order functions like map and reduce but for N-dimensional objects (e.g. arrays or tensors)? For mapping, I guess it would be a point-wise ...
1
vote
0answers
26 views

Seeking guidance on what to read for Feasibility Binary IP with ''almost total unimodular'' (-1, 0, 1)-Coefficient Matrix and No Obj Function

I am working on an algorithm in graph theory which I wish to prove it's polynomiality/NP-hardness. I am investigating a binary variable (0, 1) integer program which has the coefficient matrix ...
1
vote
1answer
57 views

How does the sweep line algorithm check for intersection using vector cross product?

I am trying my best to understand the sweep-line algorithm to find line intersections. I have understood most of the intuition except how it is calculating the intersection between 2 line segments ...
0
votes
1answer
46 views

When does Gaussian elimination solve exact 1-in-3 SAT?

Terms: A literal is a variable or its negation. A clause is a set of literals. An exact 3-in-1 clause is satisfied if an assignment of values to variables results in exactly 1 ...
0
votes
0answers
39 views

Computing structure tensors

As far as I understand, the structure tensor is: $$ M = \sum_{(x,y) \in W} \begin{bmatrix} I_x^2 & I_xI_y \\ I_xI_y & I_y^2 \end{bmatrix} = \begin{bmatrix} \sum_{(x,y) \in W} I_x^2 & \...
1
vote
1answer
31 views

Complexity of Matrix Inversion when $n-2$ Eigenvalues are the same

Suppose we have a symmetric matrix $A \in \mathbb{R}^{n \times n}$ that has $n-2$ equal eigenvalues and the other two are distinct. Question: What would be the complexity of its inversion? On the ...
1
vote
1answer
16 views

Math behind Multi-class linear discriminate analysis (LDA)

I have a question about Linear Discriminant Analysis (LDA) for the purpose of Dimensionality Reduction. So I understand for the algorithm to calculate for $k$ projection vector(s) you need to ...
3
votes
1answer
88 views

Applying SVD compression to integral point images

Suppose that we have an $m\times n$ matrix $A$ of rank $n$, whose entries are 8-bit unsigned integers obtained from a grayscale image. Now we want to apply SVD to $A$ and to use the first $k$ singular ...
1
vote
0answers
25 views

Minimum basis for the nullspace of sparse matrices

Let $A\in\mathbb{F}_2^{m\times n}$ and denote its nullspace as $V=\{x\in\mathbb{F}_2^m:xA=0\}$. The weight of a basis $B=\{b_1,\dots,b_l\}$ for $V$ is the total weight of vectors in the basis, denoted ...
2
votes
0answers
59 views

Calculating number of intersections of a horizontal line with line segments efficiently

I'm given an array $A = [a_1, a_2, ....a_n] $ using which I construct $n-1$ contiguous line segments by drawing a line from $(i,a_i)$ to $(i+1, a_{i+1})$. Now, I'm given $q$ queries in the form of $...
2
votes
2answers
536 views

Count number of pairs of elements whose product is a perfect square

Given two arrays whose elements lie between $[1,10^5]$ and the size of arrays is $[1,10^5]$, how can we find the total number of pairs of elements from these arrays such that their product is a ...
0
votes
1answer
43 views

Given a set of integers $D$ and a positive value$P$, find an algorithm to find set of integers satisfying a condition

Given a set of positive integers : $ \\ D = \{ D_1, D_2, ..., D_n\}$ and a non-negative integer $P$, where $P$ is divisible by every element in $D$, then find ...
0
votes
0answers
11 views

Best algorithm for computing the log-determinant

I am diving into some literature to understand which is the best algorithm for computing the log-determinant of a PSD matrix. So far I have found the following two papers: Large-scale Log-...
1
vote
0answers
18 views

Are there practical usage of determinants in numerical simulation?

I know the historical importance of the link between linear systems and determinants. I also know that determinants have a beautiful connection with non-singular matrices, i.e., if a matrix is non-...
1
vote
0answers
41 views

What is the complexity of finding e^(A) for a Hermitian matrix A?

If A is a hermitian matrix of size NxN .What is the order of no. of steps required to compute e^(A).How to prove it?
0
votes
0answers
7 views

Looking for good book similar Stability/Conditioning in Numerical Linear Algebra,

I am currently reading Numerical Linear Algebra by Trefethen and Bau and I am finding it quite difficult to read. In particular, I have been trying to read the sections on Floating Point Arithmetic, ...
0
votes
0answers
126 views

Check the Complexity time of Power method

Hi i have write a function in Matlab to calculate the power method and i wont to find the time complexity. ...
1
vote
0answers
20 views

Minimal subset of rows that generate smaller polyhedron

Given a matrix $[A|B]$ I want to find a minimal matrix $[A'|B'] \subseteq [A|B]$ (i.e. the rows in $[A'|B']$ are also in $[A|B]$) such that $A'x < B' \Rightarrow Ax < B$. Geometrically, I want ...
1
vote
0answers
35 views

Given a system in $\mathbb{F}_2$ in RREF, how do I find a solution of minimal norm?

I have a $12 \times 12$ (so not really large) system of linear equations in $\mathbb{F}_2$ which I got to RREF through the usual row reduction. Suppose the system has multiple solutions, and call the ...
1
vote
0answers
29 views

How do you solve a general linear diophantine equation in polynomial time (with minimization constraint)?

Given $$ a_1 X_1 + \dots + a_n X_n = b $$ where $a_i, b \in \Bbb{Z}$. How do you come up with a clearer picture of the solution set in polynomial time. Also, what I really want is to do the above,...
1
vote
0answers
15 views

Convergence of Conjugate gradient method

I have implemented my own matrix library in Java to solve fluid simulations. So I have also implemented the conjugate gradient method and I got a little bit confused. What I have done to test my CG-...
1
vote
1answer
41 views

Recover boolean vector from dot products

Question: I want to determine a boolean vector $b \in \{0,1\}^n$ consisting of zeros and ones, but cannot access it directly. I can only call a black-box computer code which will take the dot product ...
1
vote
1answer
40 views

Underlying codes for Niederreiter cryptosystems

Niederreiter cryptosystem is usually described by a parity check matrix $H$ over $\mathbb{F}_{2^n}$. The minimum distance $d$ is given by $d := min\lbrace k \text{ such that there are $k$ linearly ...
1
vote
0answers
39 views

Minimize number of math operation of a specific matrix vector multiplication?

Let's say we have a Matrix M and a column vector v like below multiply equals Assume we can only perform multiplication, addition and substraction operation. With normal approach we need 3 ...
2
votes
0answers
63 views

Calculating diagonal of inverse of sparse band-like matrix

I'm trying find an optimization for an equation related to theorem 3.5.7 from "Finite Markov Chains" by Kemeny and Snell (1976). The theorem is: $$H=(N-I)N_{dg}^{-1}$$ Where $N_{dg}$ is a diagonal ...
1
vote
0answers
47 views

How is the modular multiplication matrix unitary in Shor's Algorithm?

I have been reading papers about the construction of this matrix in Shor's Algorithm all night. The behavior of the controlled modular multiplication matrix is described as $$C U_{a^{2}}(|c\rangle|y\...
0
votes
1answer
38 views

Geometric median of two disjoint sets of points lies on line between their respective medians

I was working on a problem about geometric medians and I had an idea for a divide and conquer solution, but it would only work if a set of points, when split into two disjoint sets, and those sets ...
0
votes
0answers
54 views

How to quickly solve a linear equation for 7000 times?

I need to solve a linear equation Ax=b for 7000 times (A is sparse and complex square matrix), and at each time only 4 elements (A(i,k), A(i,m), A(j,k) and A(j,m)) are changed while all other elements ...
0
votes
0answers
36 views

How to make sure matrix completion can generate a matrix with values in expected range?

I am doing a matrix completion project. Assume that I have an incomplete matrix like ...
2
votes
1answer
37 views

Determine image of hypercube under linear map

Let $A$ be an $3\times N$ matrix (where $N$ is large) with nonnegative real entries. I'd like an algorithm for determining when a vector $v\in\Bbb R^3$ can be written as $Aw$ for some vector $w\in\Bbb ...
2
votes
1answer
160 views

Can this equation be solved in polynomial time?

I came across a more general form of this question. Can we find the value of variables in polynomial time ? Let $m = n^{2}$, there are $m$ variables ($x,y,z\ldots$) in the equation and these $m$ ...
2
votes
0answers
41 views

Check if a matrix over finite fields is superregular

Is there any practical, efficient algorithm to check if a matrix over $\mathbf{F}_{p^n}$ is superregular? It need not be theoretically polynomial, just roughly be implementable for $n=32$ and for ...
5
votes
2answers
165 views

Can this system of polynomial equations be solved in polynomial time?

I have these $n$ equations, with $n$ variables. Variables are first $n$ positive integers, constants can be any rational number including zero. Given that there is always a solution, how do we find a ...
1
vote
0answers
114 views

Confusion about the geometric interpretation of the simplex method for linear programming

In Section 7.6.2 of the textbook "Algorithms" by Sanjoy Dasgupta, Christos Papadimitriou, and Umesh Vazirani, the authors provide a geometric interpretation of the two main tasks of each iteration of ...
1
vote
1answer
78 views

What is the intuition behind the way of reading off a dual optimal solution from simplex primal tabular in CLRS?

Section 29.4 "Duality" of CLRS (3rd Edition) describes the way of reading off an optimal dual solution from the last slack form of the primal as follows: Suppose that the last slack form of the ...
2
votes
0answers
50 views

An efficient algorithm to find a linear transformation between two ternary quadratic forms

Let $\mathbb{F}_p$ be a prime finite field for $p > 2$. Consider two ternary quadratic forms $$Q_1\!: x^2 - a_1(t)y^2 - b_1(t)z^2,\\ Q_2\!: x^2 - a_2(t)y^2 - b_2(t)z^2$$ over the field $\mathbb{F}...
1
vote
1answer
95 views

What is the fastest algorithm to establish whether a linear system in $\mathbb{R}$ has a solution?

I know the best algorithm to solve a linear system in $\mathbb{R}$ with $n$ variables is Coppersmith-Winograd's algorithm, which has a complexity of $$ O\left(n^{2.376}\right). $$ How much easier is ...
3
votes
2answers
243 views

Transforming a byte with a subset of a small, fixed set of values and xor into any other value

If I have some collection of bits, -- a byte, say -- of arbitrary value then I can transform it into some other value by means of exclusive-oring it with a subset of (in this case) eight fixed values, ...
1
vote
1answer
34 views

Smallest Circuit for Square of Sparse Symmetric Matrix

I have an n by n symmetric matrix, and I would like to compute its square in as small a circuit complexity as possible. It's sparse: there are sqrt(n) nonzero entries in each row/column, so the input ...
2
votes
1answer
38 views

Sublinear Homomorphism Property Testing Counter Example

This is a homework question, so I'm not looking for answers, just general guidance. I'm looking at a Sublinear Algorithms survey where (Group) Homomorphism property testing is discussed. The case of ...
1
vote
2answers
49 views

Algorithm to solve $L_1$ optimization of $\sum_i ||\mathbf{A_i x} - \mathbf{b_i}||_1$

Is there is an efficient algorithm to solve the following optimization: $\mathbf{x}^* = \arg\min_\mathbf{x}\sum_i ||\mathbf{A_i x} - \mathbf{b_i}||_1$ for given $\mathbf{b_i}, \mathbf{A_i}\ \forall ...
0
votes
0answers
29 views

Equivalent Algorithm with Sharman Morrison inversion

I am trying to invert a matrix using Woodbury identity. The inversion using Cholesky decomposition has the following pseudo-code: For $t=1,2,...$ $(1)\;\; \text{Read}\;x_t\in\mathbb{R}^n$ ...
0
votes
0answers
32 views

Randomly choose matrices $A_{j}B = C_{j}$ with elements between 0 and 1

Problem I have $J$ matrices $C_{j}$, which are $K \times M$. Elements of each matrix $C_{j}$ are between 0 and 1. I want to randomly choose $J$ matrices $A_{j}$ and one matrix $B$ such that: ...
1
vote
1answer
159 views

Representing chained XOR operations as linear inequalities

I'm trying to solve an integer linear program (ILP) in which a constraint of the following kind must be met: $x_1 \oplus x_2 \oplus \cdots \oplus x_n = 1$ where $\oplus$ is the binary xor operator. ...
0
votes
1answer
18 views

Avoiding underflow when identifying neighbours of a cell in a grid by using modulo

I'm going through a tutorial that is using the Game of Life as example code. It has a function in it that finds the neighbor of a given cell. It is explained quickly that "When applying a delta of -1, ...
2
votes
1answer
35 views

What's the connection between the two “Fast Walsh Transform”?

First Let's take a look at the convolution $\displaystyle C _ { i } = \sum _ { j \oplus k = i } A _ { j } * B _ { k }$, and the $\oplus$represents any boolean operation. And we are able to evaluate $C$...
1
vote
1answer
38 views

Randomly choose vector b in range such that $\vec{a} \cdot \vec{b} = 1$

Given I have a $n$ dimensional $\vec{a}$. All elements of $\vec{a}$ are between 0 and a positive number $K$. $n$ is about 15 to 20. Problem I want to randomly and unbiasedly choose a vector $\vec{b}...
1
vote
0answers
42 views

Check if no linear combination is within a hypercube

Shapes Let $C$ be the unit hypercube in $\mathbb{R}^{n}$. Let $\vec{o}$ be a point in $\mathbb{R}^{n}$. Let $B$ be a $n \times m$ matrix. The columns of $B$ are a set of linearly independent vectors ...
2
votes
1answer
42 views

Randomly construct linear combination that is within bounds over two basis

Given rank deficient matrix $A$, I want to randomly construct vectors $\vec{x}$ such that: $0 \le x_{j} \le 1$ $0 \le b_{j} \le 1$ where $\vec{b} = A\vec{x}$ Matrix $A$ is about 10 x 15. I want to ...
1
vote
0answers
22 views

Sparse feasible solution $|x|_0\le k$ for system of linear inequalities $A x \le b$

Suppose the set of linear inequalities $Ax\le b$, in which $A\in\mathbb{R}^{m\times n},x,b\in\mathbb{R}^n$ is given. Is it possible to determine in polynomial time with regard to $m$ and $n$ if there ...