All Questions
Tagged with linear-algebra co.combinatorics
513 questions
6
votes
1
answer
458
views
Vector with many non-zero coordinates
Given finite field $\mathbb{F}_q$, positive integers $n$ and $k<n$. Given $k$-dimensional subspace $X$ of $\mathbb{F}_q^n$, for which $m=m(q,k,n)$ may we find for sure a vector in $X$ with at least ...
- 109k
5
votes
2
answers
312
views
Characterizing graphs whose incidence matrix has the all ones vector in its row span
Suppose we have a simple connected graph $G=(V,E)$. Then let $A$ be its $|E|\times |V|$ incidence matrix. Here I am considering the unoriented incidence matrix. I want to know when the row span of $A$ ...
- 928
4
votes
0
answers
137
views
Number of linearly independent subsets in arbitrary set
Consider $n$-dimensional vector space $\mathbb{F}_p^n$ over finite field $\mathbb{F}_p$ and a function $a: \mathbb{F}_p^n\rightarrow\mathbb{C}$. Let
$$ F(a) = \sum_{\substack{S\subset \mathbb{F}_p^n \...
- 331
4
votes
1
answer
206
views
Representing a graph's vertices as linear combinations of paths
I have a (directed graded) graph $G=(V,E)$ with two distinguished subsets of $V$: sources and destinations. I am to show that the set of indicator functions of paths starting in a source and ending in ...
- 3,513
7
votes
1
answer
461
views
Can every trace preserving isomorphism of unital self-adjoint matrix algebras be realized as conjugation by a unitary?
In this paper, Friedland shows (in Lemma 3.4) that if $\phi$ is an isomorphism of coherent algebras, then there exists a unitary $U$ such that
$$ \phi(M) = UMU^\dagger$$
for all $M$. I am wondering if ...
- 2,339
19
votes
5
answers
1k
views
List of counting proofs instead of linear algebra method in combinatorics
I've just come across this proof of the Graham-Pollak Theorem by Sundar Vishwanathan (thanks to Konrad Swanepoel's sporadic comments about it on this site), that must be called beautiful after its ...
- 19k
1
vote
1
answer
257
views
Directed graph Laplacian with exactly one negative eigenvalue
Let $G$ be a digraph with adjacency matrix $A =(A_{ij})$ where $A_{ij}=1$ if and only if there is a directed edge $i \to j$ and $A_{ij}=0$ otherwise. Let $D= (D_{ij})$ be the degree matrix with $D_{ij}...
- 11
2
votes
1
answer
450
views
Extracting a full rank matrix from a 0-1 matrix
If $A$ is a $n\!\times\!n$ $0$-$1$ matrix of rank $k<n$. If ever possible, what would be an efficient way of extracting a full rank $k\!\times\!k$ sub-matrix of $A$ by removing columns and rows of ...
- 23
1
vote
1
answer
2k
views
Determinant of discrete Laplacian
It can easy be shown by induction that the determinant of the $(N-1)\times (N-1)$ matrix
$$\begin{pmatrix}
2 & -1 & & \\
-1 & 2 & \ddots & \\
& \...
- 9,853
3
votes
1
answer
385
views
Bounds for maximum determinant of circulant matrices
The Hadamard circulant conjecture states that there do not exist circulant Hadamard matrices with more than $4$ columns.
An $n$ by $n$ Hadamard matrix where the entries are chosen from $\{-1,1\}$ ...
- 3,377
1
vote
1
answer
133
views
Reduced echelon form of sparce matrices and constructing hash function
Let $G$ be a $d$-regular graph, and $A$ be the incidence matrix of $G$. Also suppose $B$ is a reduced echelon form of $A$ such that computations are in $\mathbb F_2$. Given matrix $B$, can we find ...
2
votes
2
answers
664
views
On $XX'=I$ such that $AX=XB$ is true when $A,B\in\{0,1\}^{n\times n}$
Given real symmetric matrices $A,B\in\{0,1\}^{n\times n}$ is it true that $$AX=XB$$ has a solution of form $X$ a permutation matrix iff a solution with $XX'=I$ exists? We are over reals.
It is clear ...
- 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
2
votes
0
answers
115
views
Polynomials with positive coefficients passing through fixed points/range of Vandermonde matrices
I'll give two equivalent statements of the setup, then give my questions.
Fix integers $M \leq N$ and define the Vandermonde-like matrix $V_{M,N}[i,j] = (1 - \frac{i}{M})^{j-1}$ for $i \in \{1,2,\...
- 21
12
votes
1
answer
1k
views
Maximal Number of Pairs of Orthogonal vectors in a set of $n$ vectors in $\mathbb{R}^3$
Suppose you are given a set of $n$ non-zero vectors in $\mathbb{R}^3$. What is the maximum number of pairs of them that are orthogonal? The current guess is $\le 2n$.
EDIT: I forgot to add that no ...
- 928
1
vote
2
answers
478
views
Worst case difference in rank by column-row swapping
Given a matrix $m\in\{-1,+1\}^{n\times n}$. Consider $m^\sigma$ to be collection of all matrices obtained from $m$ by permuting rows and columns.
Consider $\mathscr{M}[m^\sigma]$ to be collection of ...
- 13.9k
3
votes
1
answer
445
views
Largest symmetric matrix given rank
Let $\mathscr{M}[n,d]$ be collection of $n\times n$ symmetric matrices with real entries from $\{0,1\}$ such that every row/column is distinct with sum of every row/column being $d$.
What is minimum ...
- 13.9k
3
votes
1
answer
85
views
Vanishing Restricted Isometric Constant
In compressed sensing, we are interested in the restricted isometry property. Suppose the design matrix is $n$ by $p$, consisting of $np$ iid $\mathcal{N}(0, 1/n)$ entries. Assume both $n$ and $p$ are ...
- 773
1
vote
0
answers
138
views
Minimum rank of certain matrices
Let $\mathscr{M}[n]$ be collection of $n\times n$ matrices with real entries from $\{0,1\}$ such that every row is distinct and every column is distinct.
What is minimum real rank of matrices in $\...
- 13.9k
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
2
votes
1
answer
177
views
Linear independence of +/- 1 strings/vectors II
Let $V=\left\{-1,1\right\}^{n}$. Consider three vectors $v_1,v_2,v_3\in V$. I would like to know whether these vectors are linearly independent over $\mathbb{Z}$. To be more precise - I need a ...
- 2,288
1
vote
1
answer
190
views
Linear independence of +/- 1 strings/vectors
Let $V=\left\{-1,1\right\}^{n}$. Consider three vectors $v_1,v_2,v_3\in V$. I would like to know whether these vectors are linearly independent over $\mathbb{Z}$. To be more precise - I need a ...
- 2,288
6
votes
1
answer
778
views
Dimension of the span of all partial derivatives of a given homogeneous symmetric polynomial $f$ and the polynomial $E(f)$
I need some help about the problem below.
Let $d\geq 4$ and $f$ a symmetric polynomial, homogeneous of degree $d$, in $n$ variables $x_1,\dots,x_n$, with real coefficients. We set
$$ E(f):=\sum_{j=1}^{...
- 307
1
vote
0
answers
54
views
Lattice-isotopic essentialization of arrangements
I'm working on a problem related to
$\textbf{Randell's isotopy theorem}$ for complex hyperplane arrangements. I have a question which seems quite obvious. However, I haven't found a rigorous proof ...
- 741
12
votes
2
answers
780
views
Determinant of a checkerboard Hankel matrix with Catalan numbers
My goal is to compute
\begin{equation}
I = \det \left(\mathbf{I} + \mathbf{A}\right)
\end{equation}
where $\mathbf{A}$ is a $n \times n$ checkerboard matrix filled with Catalan numbers:
$$
\left\{
...
- 840
1
vote
0
answers
111
views
Notions of consistency / heterogeneity in sets of vector values?
The problem
Let us consider a row vector u of size $n\in\mathbb{N}$, containing only binary values (0,1):
$$u=(u_1 \cdots u_n), n\in\mathbb{N}$$
$$\forall i \in \{1\ldots n\}, u_i \in\{0,1\}$$
I would ...
- 11
1
vote
1
answer
275
views
Dense symmetric unitary integer matrix?
Can someone give me a nontrivial example of a symmetric unitary integer matrix? I'm looking for something as dense as possible (i.e., not too many 0's); 5 <= size <= 8 would be ideal.
5
votes
1
answer
372
views
The Maximal $\ell_2$ norm of a signed sum of vectors
Suppose we have $n$ vectors in $\mathbb{R}^n.$ Consider the signed sum of these vectors:
$$U(s_1,\ldots,s_n)=s_1 v_1+s_2 v_2 + \ldots + s_n v_n$$
where $s_j$'s can only take values of $+1$ or $-1.$ I ...
- 131
10
votes
3
answers
486
views
Distinguishing combinatorial maps by their linearizations
Every (not-necessarily invertible) map $f$ from $[n]:=\{1,2,,,,.n\}$ to itself determines a linear map $L_f$ from ${\bf R}^n$ to itself that sends the basis vector $e_k$ to $e_{f(k)}$ for $1 \leq k \...
- 19.7k
3
votes
0
answers
130
views
Where does this identity involving sums of Hankel-like determinants over partitions come from?
For a partition $\lambda=( \lambda_1,\dots,\lambda_n)\vdash n$ with $\lambda_1\ge\dots\ge\lambda_n\ge0$ and any function $f:\mathbb Z\to\mathbb C$, define a Hankel-like $n\times n$ matrix $$M_f(\...
- 13.4k
3
votes
2
answers
279
views
Rank changes with matrix edits
Assume we have rank $r$ real matrix $M\in\{0,1\}^{n\times n}$ (not constrained to symmetric).
Assume $W\in\{0,1\}^{n\times n}$ is rank $1$ real matrix.
Case $1$: $M+W\in\{0,1\}^{n\times n}$.
Could ...
- 13.9k
0
votes
0
answers
89
views
Decomposing matrices to lower ranks
Given real matrix $M\in\{0,1\}^{n\times n}$ of rank $r$. How many $M_i\in\{0,1\}^{n\times n}$ of rank $s$ does one need to write $M'=\sum_{i=1}^ta_iM_i$ for some $a_i\in\Bbb R$ where maximum absolute ...
- 13.9k
1
vote
1
answer
220
views
Probabilistic statement on matrix ranks
Given $A\in\{0,1\}^{n\times n}$ with $\operatorname{rank}(A)=r=2^{O((\log_2n)^{\frac{1}{c+1}})}$.
Denote $\mathsf{1_n}\in\{0,1\}^n$ as vector with $1$s.
Does
$$\lim_{n\rightarrow\infty}\mathsf{P_{A\...
- 13.9k
2
votes
0
answers
140
views
Number of degree $k$ functions [closed]
Given a Boolean function $f:\{0,1\}^n\rightarrow\{0,1\}$, there is a real multivariate multilinear polynomial that is associated with in through interpolation.
Example: $AND(x_1,x_2,\dots,x_{n-1},x_n)...
- 13.9k
2
votes
1
answer
278
views
Distinct determinants of circulants
If $M$ is a circulant integer matrix of size $n\times n$ whose entries are randomly chosen from $\{0,1\}$ value, how many different determinants does $M$ possibly take value in?
For $n=1,2,3,4$, I ...
- 13.9k
3
votes
1
answer
1k
views
Open problems in compressed sensing
What are the main open problems in compressed sensing?
I am interested in theoretical as well as in numerical point of view.
- 6,962
3
votes
2
answers
260
views
Number of *distinct* dot products of an integer vector by elements of a hyper-rectangle
Imagine a vector $\boldsymbol{v}$ composed of integers, and the set $S$ of all integer vectors within a hyper-rectange, with one corner at the origin and other at $\boldsymbol{m}$. In other words: $S ...
- 379
1
vote
0
answers
53
views
Distributing partially known data between n parties
Assume that $n = 2r+1$. There are $n$ elements $a_1,a_2,\ldots,a_n$ from a finite field $\mathcal{F}$, and $n$ parties. Each party knows the values of at least $r+1$ elements out of those $n$ elements....
- 323
8
votes
2
answers
246
views
Are sums of 0-1 Pareto efficient vectors Pareto efficient?
Does there exist $m,n\ge1$, an $m \times n$ matrix $A$, and a vector $x \in \mathbb{R}^n$ such that:
The entries of $A$ are $\in \{0, 1\}$.
For all pairs of columns $u, v$ of $A$ the entries of $u - ...
- 388
7
votes
4
answers
1k
views
Generalized Cauchy-Binet sum over a fixed subset of indices
I originally posted this on math.stackexchange, but it quickly got buried. I removed it not too long after, thinking of rewriting it for MO, but I didn’t have a chance to post it until now. Apologies ...
- 13.6k
19
votes
1
answer
948
views
Recognize this strange expression from linear algebra?
I've come across an odd-looking expression and oh how I wish I had a more elegant description of it. Maybe someone who enjoys symmetric bilinear forms in characteristic two will recognize it? Or ...
- 13.3k
3
votes
0
answers
237
views
Multi-dimensional permanent of structured tensor
I am facing the multidimensional permanent
\begin{equation} \text{perm}(W) = \sum_{\sigma, \rho \in S_n} \prod_{j=1}^n W_{j, \sigma_j, \rho_j } \end{equation}
of a 3-tensor $W_{j,k,l}$ of ...
- 93
10
votes
2
answers
495
views
Is there a hyperplane avoiding two independent sets?
Let $V$ be a vector space over a field with $5$ elements, $A,B \subseteq V$ independent subsets. Must there be a subspace of $V$ of codimension 1 disjoint from $A \cup B$?
- 11.3k
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
1
vote
0
answers
140
views
Reduce a Combinatorial problem
It is given n sets with k vectors. (k is element-wise positive or zero)
Choose one vector of each set so that the biggest element of the sum of the chosen vectors is minimal.
What i also know but is ...
- 11
0
votes
1
answer
664
views
Kneser graphs eigenvalues
Basically, I want to prove that, in the Kneser graph (wikipedia has a good definition),$K_{n, m}$, if $n_{-}(A(G)) $ and $n_{+}(A(G))$ denote the number of negative and positive eigenvalues of A(G) ...
1
vote
0
answers
55
views
Find a common expression (parameterized by y = 1/2, 1 and 2) uniting three (rational) polynomials in k [closed]
I am seeking a common "simple" expression (preferably/presumably a sum of products of linear factors, or sum of products of low-degree factors) uniting the three polynomials (parameterized by $y=\...
- 723
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
5
votes
0
answers
604
views
The twisted kiss of the curvaceous cubic and the staid tetrahedron (references)
(Migrated from MSE)
While investigating some operators, I came across some relations between the twisted cubic curve and the tetrahedron that link together some notions in differential geometry, ...
- 10.5k
-1
votes
1
answer
200
views
Collecting terms of a linear expression with nested sums and combinatorics in coefficients
I need to collect the $\Pr(\cdot)$ terms of the following expression:
$\sum_{m=3}^{n}\frac{g_{m}\left( \cdot \right) }{\left( \sqrt{\theta \left(
1-\theta \right) }\right) ^{m}}\left[ \sum_{j=2}^{m-1}...
