2
votes
1answer
51 views

Solution to generalized Sylvester equation

I am interested in solving generalized Sylvester equations (for $X$) of the form: $$ \sum_{j=1}^k A_j X B_j^T = F, $$ where $A_j,B_j,X,F\in\mathbb{C}^{n\times n}$ and $k$, $n$ are integers. I will ...
2
votes
2answers
222 views

Finding the set of all $0-1$ vectors in an affine subspace

We are given a $0-1$ matrix $A$ with constant row and column sum, and we need to find out if there exists a $0-1$ vector in the solution space of $Ax = \mathbf{1}$ over $\mathbb{Q}$ (or $\mathbb{Z}$) ...
1
vote
0answers
140 views

Is finding a single vector in the null space as difficult as discovering the whole null space?

Let $A \in \mathbb R^{k\times n}$ be a matrix of rank $k$, where $k \ll n$. One can use Gaussian eliminations to discover $\operatorname{null}(A)$ at the cost of $O(nk^2)$. My question is: Is the ...
1
vote
0answers
26 views

Heuristic for choosing n-vectors from n-sets

my given problem is: choose n-vectors from n-sets (one vector from each set) so that the biggest element in the sum of the chosen vectors is minimal. Unfortunately the problem is NP-hard. So I'm ...
4
votes
0answers
91 views

A question on hyperplanes in partial linear spaces and hypergraphs

A partial linear space (or a linear hypergraph) is a point line geometry $(P,L,I)$ where for every pair of points there is at most one line incident with both of them. A hyperplane in a partial linear ...
2
votes
0answers
64 views

Lanczos algorithm with thick restart on a dynamic matrix

currently, I'm working on a way to compute the 2 biggest eigenvalues of a real, symmetric, huge and sparse matrix that changes a few entries from time to time. The problem should be solved using an ...
2
votes
0answers
125 views

Algorithms to compute largest gap between smallest nonzero eigenvalues of sparse symmetric matrix

I am looking mainly for implementations but also for theoretical algorithms to compute gaps between smallest positive eigenvalues of symmetric, singular matrix or real numbers. To be precise, I want ...
3
votes
0answers
152 views

Finding a basis for the (linear combinations) span of a matrix group, efficiently?

I have an algorithm whose bottleneck is the following task: Let $\mathbb{F}$ be a finite field. Given a set of $k$ invertible matrices $g_1,\dots,g_k\in GL_n(\mathbb{F})$, let $G=\langle ...
8
votes
1answer
511 views

How to check whether a positive integer can be written as linear combination of given others, where all coefficients are positive?

Let $n$, $k$ and $m_1, \dots, m_k$ be positive integers. Which is the most efficient algorithm to find out whether there are positive integers $a_1, \dots, a_k$ such that $n = \sum_{i=1}^k a_i m_i$? ...
3
votes
1answer
125 views

Is there an algorithm to compute group presentations of or find generators for the centralizer of a matrix in $GL(n, \mathbb{Z})$?

Let $M \in H \leq GL(n, \mathbb{Z})$. Is there an algorithm that computes either matrix generators or even a group presentation for $C_H(M)$ given generators or a presentation of $H$? Also is ...
7
votes
1answer
232 views

Main problems on lattice-basis reduction algorithms (such as LLL)?

What are the main open problems on lattice-basis reduction algorithms (such as LLL)? I am looking for problems satisfying the following two conditions: (a) their solution would likely be of some ...
1
vote
0answers
104 views

Row subset selection of matrix to optimize condition number

Given a matrix $\mathbf{A} \in \mathbb{C}^{N\times M}$ with $N \gg M$. This matrix results from a linear equation system and has a certain structure (however, I do not think that details provide any ...
4
votes
1answer
280 views

Checking if a binary vector lies in the affine span of given binary vectors

Let $x_1,\ldots,x_N \in \{0,1\}^D$ be $N$ binary vectors in ${\mathbb R}^D$, assumed affinely independent. Is there an efficient algorithm for determining whether a new binary vector $x_{N+1}$ is in ...
5
votes
2answers
769 views

Solve for $A$ and $B$ in $AXB=Y$

Let $R = \mathbb{Z}[x_{1}, \dots, x_{r}]$. Let $X$ be $n \times n$ matrix with entries in $R$. Let $Y$ be $m \times m$ matrix with entries in $R$ formed from $\mathbb{Z}$-linear or $\mathbb{R}$-linear ...
3
votes
0answers
187 views

(Co)limit computations for diagrams of Vector Spaces

Fix a field $K$ and consider a finite directed graph $\Gamma$ where multiple edges between a pair of vertices are allowed so long as the total number of edges is finite. Associate to each vertex $v$ a ...
2
votes
0answers
45 views

Most efficient algorithm for computing norm of the residual for the least squares problem in the rank deficient case

I have a large $m\times n$ data matrix $A$, $m>n$, and response $m$-vector $b$. I need to calculate $E = ||Ax-b||_2$ as quickly as possible, where $x$ is the least squares solution. I don't need ...
2
votes
1answer
264 views

Finding a subspace disjoint from a union of subspaces

Let $k$ be a finite field (I care about $\mathbb F_p$, especially $\mathbb F_2$) and let $V_1,...,V_N\subset k^n$ be subspaces. I want to find a subspace $S\subset k^n$ such that $S\cap V_i=0$ for ...
2
votes
2answers
248 views

Lattice reduction on an orthonormal lattice?

Suppose you are given an inner product on a vector space and given a set of linearly independent vectors, and that you have been promised that the lattice they span has an orthonormal basis. Can you ...
5
votes
0answers
339 views

Determine if a matrix is unimodular

Is deciding if an integer square matrix has determinant $\pm 1$ faster that calculating the determinant of the matrix?
12
votes
2answers
449 views

Optimizing the condition number

Suppose I have a set $S$ of $N$ vectors in $W=\mathbb{R}^m,$ with $N \gg n.$ I want to choose a subset $\{v_1, \dots, v_m\}$ of $S$ in such a way that the condition number of the matrix with columns ...
1
vote
2answers
177 views

Simultaneous Smith Normalization of a Composable Matrix Sequence

Let $\mathsf{R}$ be a PID and consider a collection of free, finitely generated $\mathsf{R}$-modules $V_1,\ldots,V_n$ along with module maps $m_j:V_j \to V_{j+1}$. That is, we have the following ...
3
votes
1answer
416 views

Does a product of matrices have eigenvalue 1

Start by fixing invertible matrics $A_1, \ldots, A_m \in \mathbb{Z}^{n \times n}$. For a sequence $i_1, \ldots, i_k$ we construct $A = A_{i_1} \cdots A_{i_k}$. We would like to know "Is 1 an ...
3
votes
2answers
1k views

Checking consistency of a system of linear equations and inequalities

I have a lot of systems of equations and inequalities of the following form: $$ a_{1,1}x+a_{1,2}y+a_{1,3}z+a_{1,4}w = 2 $$ $$ \ldots $$ $$ 0 < x < 2 $$ $$ 0 < y < 2 $$ $$ 0 < z < 2 ...
8
votes
3answers
436 views

Equitable Allocation of Individuals to Positions

I'm not a mathematician but I working on a problem that feels like it an example of a more general kind of problem and I'm hoping that someone might be able to point me in the right direction. The ...
3
votes
0answers
254 views

3-SAT and a matrix of linear forms representing a non-degenerate matrix

This is a follow-up to the previous question on the same topic. Thanks to Emil Jeřábek I can now ask a more specific question. As before, let $k$ be a field with $p$ elements. Consider the ...
4
votes
1answer
421 views

determining if a matrix of linear forms represents a non-degenerate matrix

Let $k$ be a field with $p$ elements. Consider the following computational problem Input: a natural number $n$, $n^2$ linear forms $M_{ij}$, $i,j=1,\ldots n$ in $n^2$ variables $X_{11}, \ldots ...
1
vote
1answer
377 views

Need help to find an efficient algorithm for the following problem!

Consider $x$ an n-dimensional vector with $x_i$ is integer in the range $[0 \dots k], k\in N$. Given $A_{n\times n}$ is the covariance matrix of $x$. $u$ is a given n-dimensional vector of real ...
4
votes
2answers
482 views

Algorithm for the intersection of a vector subspace with a cone of non-negative vectors

Hi, I would like to know whether there is some more effective way of how to compute an intersection of a vector subspace of $\mathbb{R}^{n}$ with a cone of vectors with non-negative entries than the ...
0
votes
1answer
876 views

True divide and conquer inversion of large matrices

In http://math.stackexchange.com/questions/2735/solving-very-large-matrices-in-pieces there is a way shown to solve matrix inversion in pieces. Is it possible to turn it into a true divide and conquer ...
3
votes
1answer
317 views

Mathematical Programming with other Algebras than Linear

Linear Programming is strongly entwined with linear algebra, as are many of its generalizations under the heading of mathematical programming / convex optimization. What analogies are there for ...
2
votes
1answer
174 views

Computing a generating set of the kernel of a module

Crossposted from math.stackexchange, since I'm not getting any answer and I think the question is suitable here. Given a generating set of a $\mathbb{Z_k}$-module $M \subseteq {\mathbb{Z}_k}^n$, is ...
13
votes
2answers
914 views

Seeking proof for linear algebra constraint problem.

Given a symmetric real matrix with a zero diagonal $M$, I am trying to find a diagonal matrix $D$, such that the matrix $M + D$ is positive definite, and $(M+D)^{-1}$ has a diagonal consisting of all ...
1
vote
1answer
2k views

Detection of Redundant Constraints

Suppose I pose the following query to a constraint logic programming system: ?- Y <= 6 - X, Y <= (- 4) + 4 * X, Y <= 4 + X / 3. Are there systems that would recognize the last inequality as ...
6
votes
6answers
3k views

Fast evaluation of polynomials

Hello everybody ! I was reading a book on geometry which taught me that one could compute the volume of a simplex through the determinant of a matrix, and I thought (I'm becoming a worse computer ...
2
votes
1answer
247 views

Doing column permutation under row overlap constraint

In coding theory, there are parity-check codes whose parity-check matrices $H$ are generated via column permutations. For instance, the binary LDPC codes constructed in Gallager's 1962 IRE Trans paper ...
5
votes
4answers
936 views

Determining a recurrence relation

I would like to solve the general problem of determining a linear recurrence relation that fits a given integer sequence of length $n$, or stating that none exists (with fewer than $n/2-k$ ...
2
votes
0answers
158 views

Recovering a linear map from a non-linear approximation

The problem described here is algorithmic. We are given "black box access" to a map $f:R^d\to R^d$. By this we mean that one may query the value of $f(v)$ for an arbitrary $v\in R^d$. We assume that ...
0
votes
1answer
253 views

[Matrices over Z] - An algorithm for calculating the diagonal with elementary operations

Dear mathoverflow, Let $ \left( \begin{array}{cc} a & b \newline c & d \end{array} \right) $ be a matrix with $a, b, c, d \in \mathbb{Z}$, $\gcd(a,b,c,d) = 1$ and $ad - bc = \pm N$, with $N ...
0
votes
2answers
720 views

Fast algorithms for computing nullspace of a positive semidefinite matrix over Z

Let $A \in \mathbb{Z}^{n \times n}$ be a positive semidefinite sparse matrix. I am looking for asymptotically fast algorithms for computing the nullspace basis of $A$ (or just random elements in the ...
2
votes
0answers
237 views

When is polytope compatible with network flow?

A linear program is the problem of optimizing an linear objective function within some polytope $A$ over $\mathbf R^n$. My question is motivated by the question of when a linear programming problem ...
7
votes
1answer
641 views

Best way to find a closest vector in a lattice

Let $v_1,\ldots,v_n$ be linearly independent vector in $\mathbb{R}^n$, and let $\Lambda=\oplus_i^n \mathbb{Z}v_i$. The question is, given a vector $w$ find the element $v$ of the lattice $\Lambda$ ...
-3
votes
1answer
578 views

Eliminating redundant linear constraints? [closed]

I have an NxN matrix of linear constraints that is not of full rank. In other words, some of the constraints are linear combinations of other constraints. The "standard" linear algebra tools ...
1
vote
1answer
2k views

Bidiagonalization and SVD of matrix

I can't find a single solid explanation of how to implement this -- whitepapers too detailed/confusing. Closest I came to an answer was this: ...
3
votes
1answer
1k views

SVD complexity for structured sparse matrices

Hello, For an $n \times n$ real matrix, the SVD (Singular Value Decomposition) algorithm is $O(n^3)$. I have large matrices (say $10,000 \times 10,000$) that only have elements on few diagonals, i.e. ...
2
votes
0answers
256 views

Integer relation detection for Subset Sum or NPP?

Is there a way to encode an instance of Subset Sum or the Number Partition Problem so that a (small) solution to an integer relation yields an answer? If not definitely, then in some probabilistic ...
6
votes
2answers
529 views

To what extent can algorithms in undergraduate linear algebra be made continuous/polynomial/etc.?

I feel like many of the algorithms that I learned — indeed, that I have taught — in undergraduate linear algebra classes depend sensitively on whether certain numbers are $0$. For ...
5
votes
2answers
399 views

Other norms for Lattice reduction techniques (LLL, PSLQ)?

LLL and other lattice reduction techniques (such as PSLQ) try to find a short basis vector relative to the 2-norm, i.e. for a given basis that has $ \varepsilon $ as its shortest vector, $ \varepsilon ...
21
votes
8answers
9k views

Fast Matrix Multiplication

Suppose we have two $n$ by $n$ matrices over particular ring. We want to multiply them as fast as possible. According to wikipedia there is an algorithm of Coppersmith and Winograd that can do it in ...
6
votes
2answers
3k views

Solving a system of linear inequalities — what is the dimension of the solution set?

It is well known how to solve a system of linear equations $A{\bf x} = {\bf b}$, but how do we solve a system of linear inequalities $A{\bf x} \leq {\bf b}$? For the applications I have in mind the ...
10
votes
0answers
282 views

Matroids with prescribed independent sets

Let $A$ be a finite set. Let $B$ be a family of subsets of $A$. We are interested in a matroid with a minimum rank such that every element of $B$ is independent. The answer is obvious - a uniform ...