All Questions
21 questions
5
votes
2
answers
189
views
Bisymmetric Hadamard matrices
Definitions: An $n\times n$ Hadamard matrix is a matrix whose entries are either $1$ or $−1$ and whose rows are mutually orthogonal.
A symmetric matrix is a square matrix that is equal to its own ...
- 696
2
votes
0
answers
81
views
Degeneracy and the "Linear Degeneracy Testing" problem
The Affine Degeneracy problem is about deciding whether $n$ given points in $\mathbb{R}^d$ (or $\mathbb{Q}^d$) are "in general position". i.e. there is no $d+1$ tuple of points which lies in ...
- 153
2
votes
2
answers
330
views
Polynomial time algorithm for rigid graph isomorphism
We found, implemented and tested algorithm
for graph isomorphism and it appears to be polynomial
time if the graph is rigid.
Q1 Is the algorithm below correct and polynomial time for rigid graphs?
A ...
- 25.4k
3
votes
0
answers
148
views
Linear combinations of special matrices
I am a hobby computer scientist and I have a problem to which I am searching an efficient algorithm.
Given an integer n, we want to combine some square input-matrices of size n in a way that is ...
- 73
4
votes
1
answer
209
views
Finding a binary variable assignment to make a matrix with variables singular (over F_p)
Consider a square matrix defined over a finite field $M\in\mathbb{F}_p^{n\times n}$ having the following form
$$M=\begin{bmatrix}a_{11}+b_{11}x_1&a_{12}+b_{12}x_1&\dots&a_{1n}+b_{1n}x_1\\...
- 153
1
vote
0
answers
209
views
Solution to system of linear equations
Input: System of linear equations $$A[x_1,\dots,x_{t}]=b$$ where number of equations is at least number of variables but independence is not guaranteed. However there is atmost one non-negative ...
- 13.9k
0
votes
0
answers
81
views
Constructing set with maximal independent subset
What is the minimal $m$ such that there exists a set $A = \{a_1,...a_n\}$ of vectors : $a_i \in \{0,1\}^m$ ($n$ is given) such that every subset of vectors of size $k$ is independent, but only with ...
- 51
1
vote
1
answer
221
views
How to find all minimal dependent sets of a set of vectors effectively?
In my research, I need to find the set of all minimal dependent sets of a given set of vectors. One method is to check every subset of the given set. But this method is very slow when the set of ...
- 6,201
4
votes
1
answer
96
views
Separate the trivial partition by a linear hyperspace
Let $e=[1,1,\ldots,1]\in\mathbb{Z}^n$. I am looking for a way to find a vector $a\in\mathbb{Z}^n$ such that:
$\langle a,e\rangle=0$ and
for every nonnegative $v\in\mathbb{Z}^n$ such that $\langle e,v\...
- 3,041
2
votes
0
answers
113
views
Complexity of tensor decomposition vector over $\Bbb F_q$ or $\Bbb Z$
Suppose we have a matrix $$T\in\Bbb K^{n^k\times m}$$ and a target vector $v\in\Bbb F_q^m$ where $m<n^k$ and $1<k$ holds.
We need to find $k$ vectors $u_1,\dots,u_k\in\Bbb K^n$ such that $$v=...
- 13.9k
5
votes
1
answer
255
views
Is this subset-sum-type problem discussed in the literature?
Let $y \in \mathbb{Z}_+^n$, with $y_1 < \dots < y_n$. I am interested in finding a 0-1 matrix $A$ and $x \in \mathbb{Z}_+^m$ s.t. $m$ is minimal and $Ax = y$, where I am guaranteed that at least ...
- 15.4k
5
votes
1
answer
518
views
How many random matrices does it take to generate a matrix algebra?
Let $\mathbb{F}$ be a finite field.
Let $A\le \mbox{Mat}_n(\mathbb{F})$ be a matrix algebra.
Is there a good bound on the number $k$ of random elements $a_1,\dots,a_k\in A$
that one needs to take ...
- 3,104
4
votes
2
answers
383
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,197
5
votes
0
answers
235
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 ...
- 1,197
8
votes
3
answers
510
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 ...
- 317
3
votes
0
answers
527
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 ...
- 3,897
4
votes
1
answer
842
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 X_{...
- 3,897
22
votes
9
answers
17k
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 ...
- 1,654
5
votes
4
answers
2k
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$ ...
- 9,114
0
votes
1
answer
340
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 &...
- 11
12
votes
0
answers
349
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 ...
- 1,791