All Questions
Tagged with linear-algebra discrete-geometry
44 questions
7
votes
2
answers
244
views
Prove that $ n \leq d+1 $ under ordering constraints in $\mathbb{R}^d$
Let $x_1, \dotsc, x_n \in \mathbb{R}^d$ and $\theta_1, \dotsc, \theta_n \in \mathbb{R}^d$ be vectors such that for every $k \in [n]$, the following inequality holds:
$$
\langle x_k, \theta_k \rangle &...
0
votes
0
answers
38
views
Sequence of projections that alters a $2^d$ tuple of points to a hyperparallelepiped
Suppose we have a $2^d$ tuple $\{ x_i \}_{i=0}^{2^d-1}$ of points in some $\mathbb{R}^n$. I would like to shift the points of this tuple in some controlled way, so that the final $2^d$ tuple $\{ y_i \}...
- 820
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
3
votes
1
answer
210
views
Exponential growth of shortest vector norm for successive lattices corresponding to powers of a matrix
Let $A\in M_{2\times 2}(\mathbb{Z}) $ be a two by two integer matrix such that $0,\pm 1$ are not eigenvalues of $A$ and $\left|\det(A)\right|>1$. I am interested in the growth of the norm shortest ...
1
vote
0
answers
69
views
Convolutions of (m)-associahedra and (m)-noncrossing partition polynomials--combinatorial proofs?
I'm looking for combinatorial proofs of the convolutional identity COP below and its specializations I) and II).
(Edit 6/2/2023: A combinatorial proof is sketched in a blog post by Mike Spivey of a ...
- 10.5k
8
votes
2
answers
528
views
Number of matrices with unit determinant and fixed sum of elements
Question. Let $\mathcal{M}_3$ be the set of $3\times 3$ matrices with non-negative integer entries and unit determinant. What is the number of $M\in \mathcal{M}_3$ with fixed sum of entries? What is ...
- 577
2
votes
0
answers
233
views
Do you know this formula for the scalar product in barycentric coordinates?
I've found a formula for a scalar product in barycentric coordinates which I think is pretty cool. I hope that it's new. Is it?
Suppose that you have points $x_1,\dots,x_n$ sitting in general position ...
- 1,048
7
votes
0
answers
254
views
Set of unit vectors such that among any three there is an orthogonal pair
I was fascinated by the solutions of Problem 8 of the IMC 2021 contest, which can be summarized as:
Theorem 1. Let $v_1,\dotsc,v_N$ be distinct unit vectors in $\mathbb{R}^n$ such that among any three ...
- 105k
2
votes
0
answers
57
views
Common basis property
Let F be a field and let $U_1, \ldots, U_k$ be subspaces of $F^n$. Say that $U_1, \ldots, U_k$ has a common basis if there is a basis $b_1,\ldots,b_n$ of $F^n$ such that each $U_i$ is a span of some ...
- 965
3
votes
1
answer
525
views
VC dimension of vector spaces
Does the collection of all subspaces of a fixed finite-dimensional vector space have bounded VC dimension?
Could someone please provide references for this question?
- 397
5
votes
2
answers
134
views
Is there a non-orthogonal linear deformation of a polytope that preserves edge-lengths and vertex-origin-distances?
Is there a polytope $P\subset\Bbb R^d$ (convex hull of finitely many points, not contained in a proper affine subspace), and a linear, but non-orthogonal transformation $T\in\mathrm{GL}(\Bbb R^d)\...
- 13.6k
16
votes
1
answer
537
views
Balls in Hilbert space
I recently noticed an interesting fact which leads to a perhaps difficult question. If $n$ is a natural number, let $k_n$ be the smallest number $k$ such that an open ball of radius $k$ in a real ...
- 2,049
7
votes
1
answer
299
views
Lipschitz-continuity of convex polytopes under the Hausdorff metric
Recently, I proved the following Lipschitz-continuity like result for convex polytopes:
Let $A\in\mathbb R^{m\times n}$ and $b,b'\in\mathbb R^m$ be given such that $\{x\,:\,Ax\leq 0\}=\{0\}$ (which ...
6
votes
2
answers
1k
views
Division of space by hyper-planes
It is a well known and lovely result that the maximum number of regions that $\mathbb R^{k}$ (with $k$ positive) can be divided into by $n$ hyperplanes is given by
$$1+n+\binom{n}{2}+\cdots+\binom{n}{...
- 30.1k
2
votes
1
answer
150
views
Intersection of a lower dimensional space and a discrete set
Let $H\subset \mathbb{R}^n$ with dimension ${\rm dim}(H)=\ell<n$; let $S$ be a finite subset of reals.
My question is the following. Is it correct to say,
$$
{\rm card}(H \cap V)\leqslant |S|^\...
- 1,096
3
votes
1
answer
291
views
How to find the vertices of the set $\{v_i\in \mathbb{R}:a_1\ge v_1\ge v_2\ge \cdots\ge v_n\ge 0,\ q_2\le \sum_{i=1}^n p_iv_i\le q_1\}$
I am given a set of inequalities $v_1\ge v_2\ge \cdots\ge v_n\ge 0$, $q_2\le \sum_{i=1}^n p_iv_i\le q_1$, with $\{p_i\}_{i=1}^n,\ q_1,q_2$ positive reals, and only one bound for the coordinates: $v_1\...
1
vote
0
answers
254
views
Defining a notion of “volume of its lattice” for non-rational subspaces
Let $V\subseteq \Bbb R^n$ be a vector subspace. If $V$ is rational, i.e. has a basis consisting of elements in $\Bbb Z^n$, then there’s a well-defined notion of the “volume of the lattice of V”:
$$\...
- 3,079
5
votes
0
answers
291
views
Can we represent partitions by mutually parallel lines in the plane?
Lately I have become interested in the following idea: Suppose $n$ is a positive integer and $[n]=\{1,2,3,...,n\}$. Suppose we have 3 distinct partitions $b$, $g$, and $r$ of $[n]$. Assume that the ...
- 1,277
2
votes
0
answers
184
views
Can projecting a simplex onto orthogonal subspaces exposes the same vertices and edges?
Given the regular $n$-dimensional simplex $S\subset\Bbb R^n$ with $n\ge 4$, as well as two orthogonal subspaces $V,W\subset\Bbb R^n$ of dimension $\ge2$ (not necessarily of same dimension, not ...
- 13.6k
3
votes
1
answer
263
views
Size of a minimal non-negative conic basis
Suppose $v_1,\dots,v_n \in \mathbb{R}^k$ are entry-wise non-negative (column) vectors with $k<n$. Let $r \leq k$ be the non-negative rank of the matrix $V = [v_1 v_2 \cdots v_n]$ (i.e., the ...
9
votes
2
answers
763
views
Parallelepiped is defined by the volumes of its faces
Let $v_1,...,v_n\in \mathbb{R}^n$ be linearly independent. The parallelepiped defined by these vectors is $P(v_1,...,v_n)=\{\sum_{i=1}^{n}\alpha_i v_i|~0\le\alpha_i\le 1\}$. Observe that while the ...
- 5,529
5
votes
1
answer
172
views
A combinatorial question on complete graphs and polynomials
Let $K_n$ denote the complete graph on $n$ vertices. Let us denote the vertices simply by $1,\ldots,n$. Suppose that, for each edge $ij$, with $1\leq i<j \leq n$, we assign an ordered basis $(p^+_{...
- 5,215
1
vote
1
answer
126
views
a linear programming problem
Recently I have a conjecture on decomposing a linear program into smaller ones. I have tested it in Mathmatica by a lot of examples. However, I cannot prove it. I will appreciate if someone can give ...
- 467
5
votes
1
answer
394
views
Disjoint union of affine subspaces contains a larger affine subspace
I'd like to say that a large structured subset of the $n$-dimensional Boolean cube $\{0,1\}^n$ contains a non-trivial affine subspace. To be more specific, I want to prove/disprove that for some ...
- 211
2
votes
2
answers
505
views
Maximal number of intersecting subspaces of a finite dimensional vector space
For a given $k,n$ such that $0<k \leq n/2$, is there a number $N_{n,k}$, such that if one has $N$ different $k$-dimensional subspaces $V_1, V_2,...,V_N$ in $\mathbb{R}^n$ satisfying:
1) $\bigcap_{...
- 1,101
3
votes
0
answers
189
views
Is there a reasonable way to check intersection of these set of vectors?
Given $a,m,n,t\in\Bbb Z$, with $n=m^t$ and $a$ arbitrary, and given $\mathbb{Z}$-linearly independent vectors $v_1,\dots,v_n\in\Bbb Z^n$, and an arbitrary vector $w\in\Bbb Z^n$, such that $$\langle ...
- 13.9k
3
votes
1
answer
81
views
Polytopes that are just defined by ordering the variables
I am working with a polytope with a very specific structure, namely that it is characterized entirely by placing the variables, or the variables plus constants, or just constants, in a particular ...
- 4,049
0
votes
1
answer
81
views
Can convex combinations of indicator functions for pairwise non-disjoint sets unordered by inclusion dominate one another?
Let $N$ be a finite subset of the naturals. Let $P$ be a set of subsets of $N$ such that:
1) $P\neq \varnothing$,
2) $\forall x\in P, |x| >1$,
3) $\forall x,y\in P,$ if $x\neq y$, then $x\not\...
- 3
1
vote
0
answers
71
views
Name for a Specific Planar Linear Transformation
Is there a name for linear transformations of the plane, that make $4$ points in general convex configuration co-circular, with the biggest circle through those points and, how can they be determined ...
- 13.2k
1
vote
0
answers
73
views
Is there any notion of a slack-matrix (and its rank) for a hyperplane arrangement?
I am assuming that the common lineality space of the hyperplane arrangement has already been factored out. So we are looking at an ``effective" arrangement in lower dimensions where all the polyhedra ...
- 2,246
5
votes
0
answers
311
views
Biggest (or large) rectangle in a polytope
I need an efficient method to construct a (hyper)rectangle inside a polytope with a lot of dimensions (say $100 < d < 1000$). Ideally I'd want the biggest possible rectangle, but as I don't ...
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
1
vote
0
answers
109
views
An exact fraction of a matrix
Let $A$ be a $n \times m$ real matrix with $n<<m$ and of rank $r<n$. It is known that $A$ has exactly two distinct non-zero singular values: $\sigma_{\max}$ and $\sigma_{2}$, and also that $\...
- 6,962
1
vote
1
answer
296
views
Deducing Linear Inequalities
Let $X_1,X_2,\ldots,X_n $ be indeterminates. Denote by $S$ the set of all linear inequalities of the form
$X_{i_1}+X_{i_2}+\ldots+X_{i_k} \geq k,$
with $k \in \{ 1,2,\ldots,n \}$ and $1 \leq i_1< ...
- 185
3
votes
0
answers
107
views
pavings and quadratic forms
Hi,
let $L$ be a lattice isomorphic to $\mathbb{Z}^r$ for some positive integer $r$ and $E=L\otimes \mathbb{R}$.
An integral paving in $E$ is a set $\Sigma$ of integral polytopes (the vertices are ...
- 31
11
votes
2
answers
797
views
Three half circles on the plane may not meet nicely
Let $H$ denote the union of the northern hemisphere of the unit circle $S^{1}$ with the interval $[-1,1]$ on the $x$-axis. That is, $H=\{(x,\sqrt{1-x^{2}}):-1\le x\le 1\}\cup\{(x,0):-1\le x\le 1\}$
...
- 2,136
16
votes
1
answer
774
views
Minimizing the excursion of a sum of unit vectors
I have $n$ unit-length vectors $v_i$ in $\mathbb{R}^3$, whose
sum is zero:
$$ v_1 + v_2 + \cdots + v_n = 0 \; .$$
Now I form the closed polygon $P$ in space by placing them head to tail.
So the ...
- 151k
52
votes
2
answers
3k
views
vector balancing problem
I believe the solution posted to the arXiv on June 17 by Marcus, Spielman, and Srivastava is correct.
This problem may be hard, so I don't expect an off-the-cuff solution. But can anyone suggest ...
- 42.8k
3
votes
1
answer
471
views
from affine matroid to measures
Let $S$ be an arbitrary finite spanning subset of $\mathbb{R}^d$ of cardinality $N$. Let
$W(S)$ be the formal $\mathbb{R}$-vector space generated by all $d$-dimensional
simplices (i.e. bases of the ...
- 14k
4
votes
0
answers
189
views
Slices of Simplices that are Simplices, Reference?
I am trying to find a reference for the following fact. It is elementary and not hard to prove, but I haven't been able to find the question treated anywhere.
Let $A$ be an $l\times n$ matrix with ...
- 41
4
votes
1
answer
491
views
Generalization of the "double cap conjecture" to a vector space with complex field
The conjecture that I proposed in
Maximal set on hypersphere that does not contain pairs of orthogonal vectors
is in fact known as the "double cap conjecture", as noted by Guillaume Aubrun.
See for ...
- 1,207
8
votes
0
answers
544
views
Maximal set on hypersphere that does not contain pairs of orthogonal vectors
Let R be a region on a hypersphere. Each point A of the hypersphere
is associated with a vector pointing to A and with origin at
the centre of the hypersphere. So let me identify each point with a
...
- 1,207
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
15
votes
3
answers
1k
views
Representation of vectors in $\mathbb{R}^2$ via differences of small vectors.
Is the following fact true?
Let $v_1,\ldots, v_k \in \mathbb{R}^2$, $\|v_i\|\leq 1$, be vectors that add up to zero. Does there exist a permutation $\sigma\in S_k$ and vectors $w_1,\ldots, w_k \...
- 1,284