All Questions
57 questions
96
votes
36
answers
17k
views
The concept of duality
I have been thinking for sometime about asking this question, but because I did not want to have two "big-list" questions open at the same time, I did not ask this one. Now its time has come....
49
votes
4
answers
4k
views
Why is there a duality between spaces and commutative algebras?
1) The category of affine varieties over $\mathbb{C}$ is equivalent to the opposite category of finitely generated reduced algebras over $\mathbb{C}$. The equivalence associates to an affine variety ...
- 9,481
12
votes
1
answer
5k
views
Closest 3D rotation matrix in the Frobenius norm sense
Given a 3 by 3 matrix $M$ I would like to find the rotation matrix $R$ minimizing the Frobenius norm:
\begin{equation}
\|R-M\|_F
\end{equation}
Is there a closed form solution for $R$, or is it ...
- 561
11
votes
3
answers
6k
views
Random Sampling a linearly constrained region in n-dimensions...
Hi,
So here is my problem:
Given a nonlinear, discontinous, cost function $f(x_1,x_2,..,x_N)$ along with linear constraints $x_n \ge 0, \forall n$
$x_n \le c_n$
and $\sum_{n=1}^N x_n = 1$ find an ...
- 113
6
votes
6
answers
3k
views
Circumference of Convex Shapes
Here is a puzzle I found in Mitteilungen der DMV (roughly, "Letters of the German Society of Mathematicians"), issue 19/2011. It was posed by Alfred Schreiber in "Wie man Hasen fangt" (How to catch ...
3
votes
1
answer
328
views
LP Constraints for Connected Subgraphs of Fixed Size
Question:
how can the connectedness-constraint for a subgraph, that is induced by a proper subset $W\subset V$ of the vertices of $G(V,E),\ |V|=n,\ |W|=m$, be formulated in a $LP$ or $ILP$?
...
- 13.2k
27
votes
5
answers
2k
views
Is the matrix $\left({2m\choose 2j-i}\right)_{i,j=1}^{2m-1}$ nonsingular?
Suppose we have a $(2m-1) \times (2m-1)$ matrix defined as follows:
$$\left({2m\choose 2j-i}\right)_{i,j=1}^{2m-1}.$$
For example, if $m=3$, the matrix is
$$\begin{pmatrix}6 & 20 & 6& 0 ...
- 1,121
19
votes
2
answers
2k
views
Is the tensor product of polyhedra a polyhedron?
Conventions: A polytope in a finite-dimensional $\mathbb R$-vector space $V$ is defined to be a convex hull of finitely many points in $V$. A polyhedron in a finite-dimensional $\mathbb R$-vector ...
- 33.8k
17
votes
3
answers
2k
views
The minimum of a sum of absolute values of inner products in $\mathbb{R}^d$
Consider a collection of unit vectors $v_1, \ldots, v_n$ in $\mathbb{R}^d$ (we think of $n$ being much larger than $d$). I would like to minimize the sum:
$$\sum_{i\neq j}|\langle v_i,v_j\rangle|.$$
...
- 2,288
16
votes
1
answer
2k
views
Questions about spectra of rings of continuous functions
I have been thinking a bit about rings of continuous functions of various kinds -- how they motivate the more modern notion of the Zariski topology on the prime spectrum as well as how they fit into a ...
- 65.4k
11
votes
1
answer
524
views
Elementary proof of a triangular grid lemma
I am looking for an elementary proof of the following lemma, which concerns what Green and Tao call "triangular grids" (see arXiv:1208.4714).
Let $a_1$, $a_2$, $a_3$, $a_4$, $b_1$, $b_2$ be six ...
- 1,174
8
votes
1
answer
1k
views
Compactness of the unit ball of a Banach space for topologies finer than the weak* topology
Let $(\mathcal{X} , \|\cdot \|_\mathcal{X})$ be a Banach space and $\mathcal{X}'$ its topological dual. We denote by $\| \cdot \|_{\mathcal{X}'}$ the dual norm and define also the topological dual $\...
- 2,306
5
votes
3
answers
1k
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 ...
4
votes
1
answer
3k
views
optimization of inverse matrix with constraint on matrix elements
everyone! I have this optimization problem with constraint.
$D$ and $T$ are symmetric matrices, where T is known and D is the unknown parameter.
$x$ and $v$ are two known p-dimensional vectors.
The ...
- 49
4
votes
1
answer
8k
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
...
Countably Infinite
3
votes
0
answers
76
views
Absolute continuity of $t \to \lVert u(t) \rVert^2_{H}$ and Gelfand triple : are they equivalent?
Let $V$ be a separable Banach space and $H$ be a separable Hilbert space such that
\begin{equation}
V \subset H \subset V'
\end{equation}
and the inclusion maps are continuous with dense images. Here $...
- 3,477
3
votes
2
answers
827
views
Why is the norm map dual to restriction under Tate local duality?
Let $L/K$ be a finite Galois extension of nonarchimedean local fields, and let $A$ and $A^t$ be dual abelian varieties over $K$. Tate local duality tells us that $A^t(K)$ and $H^1(K, A)$ are ...
- 1,103
2
votes
0
answers
105
views
Optimization over a convex cone generated by a set is equal to optimization over the set
Within my research I found an important doubt and that prevents me from advancing, the context of my doubt is as follows:
We considerer the following optimization problem
$$
\left\{\begin{array}{cl} \...
- 159
35
votes
12
answers
3k
views
No canonical isomorphism [duplicate]
I thought that it would be interesting to collect into a big list various instances of isomorphic structures with no preferred isomorphism between them. I expect the examples to be interesting since ...
29
votes
6
answers
8k
views
How to find a closest integer point to the intersection of two lines?
Here's a question that originates from StackOverflow.
Given are two lines on a plane, specified by equations ($a x + b y = c$) with integer coefficients. The lines aren't parallel and they don't ...
- 391
19
votes
4
answers
1k
views
Applications of linear programming duality in combinatorics
So, I know that one can apply the strong LP duality theorem to specific instances of maximum flow problems to recover some nontrivial theorems in combinatorics, such as Hall's theorem, Koenig's ...
- 997
18
votes
3
answers
3k
views
Deciding membership in a convex hull
Given points $u, v_1, \dots,v_n \in \mathbb{R}^m$, decide if $u$ is contained in the convex hull of $v_1, \dots, v_n$.
This can be done efficiently by linear programming (time polynomial in $n,m$) in ...
- 667
16
votes
3
answers
1k
views
Can a convex polytope with $f$ facets have more than $f$ facets when projected into $\mathbb{R}^2$?
Let $P$ be a convex polytope in $\mathbb{R}^d$ with $n$ vertices and $f$ facets.
Let $\text{Proj}(P)$ denote the projection of $P$ into $\mathbb{R}^2$.
Can $\text{Proj}(P)$ have more than $f$ facets?
...
- 163
12
votes
1
answer
591
views
Uniqueness of dualizing objects
One definition of (symmetric) star-autonomous category is as a closed symmetric monoidal category $(C,\otimes,I,\multimap)$ equipped with an object $\bot$ such that all double-dualization maps $A \to (...
- 66.8k
10
votes
1
answer
411
views
Network flows with capacities on pairs of edges
Take a standard network flow problem: a directed graph with nonnegative capacities on each edge, a source $s$, a sink $t$. We all know how to find the maximum flow from $s$ to $t$.
Now add edge-pair ...
- 37.7k
10
votes
1
answer
1k
views
Characterization of schemes whose dualizing complex is perfect
I'm wondering if there is a characterization of schemes over a a field $k$ whose dualizing complex is a perfect complex in terms of singularities. E.g. on a proper Cohen-Macauley scheme over a field, ...
- 5,052
10
votes
2
answers
3k
views
How do you tell if a system of linear inequalities has a solution?
A naive solution would be to optimize a dummy variable via linear programming and see if a result is returned. I imagine there must be a more direct way.
- 693
10
votes
3
answers
2k
views
Dual cell structures on manifolds
Suppose that $M$ is a compact manifold without boundary (smooth if you like), and suppose further that $M$ is equipped with a regular CW-complex structure. Denote the face poset of this CW-complex by $...
- 7,857
9
votes
1
answer
295
views
Definition of packing property
Definition 1:
A clutter $C$ is said to have the packing property if $C$ and all of its minors satisfy the König property.
where,
vertex cover of $C$ is a set of vertices that have non-empty ...
- 381
9
votes
1
answer
2k
views
Uniform sampling from general simplex with a twist
This is part of a question I had asked elsewhere, and then some of the links redirected me to CS stack exchange.
Given $0\leq a_1\leq\dots\leq a_D\leq1$ (all strictly positive), I want to draw points ...
- 221
9
votes
2
answers
341
views
Are there centrally-symmetric self-dual polytopes in dimension $d> 4$?
A convex polytope $P\subset\Bbb R^d$ is centrally symmetric if $-P=P$. It is self-dual (or better, self-polar?) if its polar dual $P^\circ$ is congruent to $P$, that is, there is a map $X\in\mathrm O(\...
- 13.6k
8
votes
2
answers
429
views
Comparison: Formal Wirthmüller isomorphism of Fausk-Hu-May vs. Balmer et. al
$\newcommand{\Cc}{\mathcal{C}}$
$\newcommand{\Dd}{\mathcal{D}}$
$\newcommand{\tensor}{\otimes}$
$\DeclareMathOperator{\Sp}{Sp}$
This question is about comparing the approaches for a formal Wirthmüller ...
- 556
7
votes
2
answers
1k
views
Is a given point in the interior of the convex hull of a given finite collection of points?
Suppose I have the convex hull $P$ of a finite collection of points in $\mathbb{R}^d,$ and I want to see whether a point $p$ is contained in $P.$ This is a standard (some would say the standard linear ...
- 96.4k
7
votes
2
answers
269
views
Double dual of free $\mathbb{Z}_{(p)}$-modules
For an abelian group $A$, put $DA=\text{Hom}(A,\mathbb{Z})$ and $D_{(p)}A=\text{Hom}(A,\mathbb{Z}_{(p)})$. It is a theorem of Specker that when $A$ is free abelian of countable rank, the natural map $...
- 56.9k
7
votes
2
answers
844
views
Criterion for being reflexive via Ext
In this question it was claimed that if a module $M$ over a noetherian domain $R$ satisfies $\rm{Ext}^i(M,R)=0$ for $i=1,2$, then $M$ is reflexive. Is this true? Does someone know a reference or a ...
- 3,031
6
votes
0
answers
133
views
The metric gives the optimal element in a class
In geometry there is plenty of examples in which the following happens:
Some elements are considered equivalent, in some topological or algebraic sense
We take the quotient
The metric is usually not ...
- 2,129
6
votes
2
answers
8k
views
Existence/Uniqueness of Nonnegative Solutions of Linear Systems of Equations
Suppose we have an $m$x$n$ matrix $A$, with $m\lt n$, and an $m$x$1$ vector $b$. Are there existence and uniqueness conditions characterizing nonnegative solutions of the system of linear equations $...
6
votes
3
answers
1k
views
opposite category
In the 2-category Cat of small categories, for each category $C$ (an object of Cat) there is also the dual category (I dare not write "dual object") $C^{op}$.
Is ${op}$ the instance in Cat of a more ...
- 476
6
votes
1
answer
609
views
Attempt at applying linear programming to the partial sums of the Möbius inverse of the Harmonic numbers
Let $a(n)$ be the Dirichlet inverse of the Euler totient function:
$$a(n) = \sum\limits_{d|n} d \cdot \mu(d) \tag{1}$$
and let the matrix $T(n,k)$ be:
$$T(n,k)=a(\gcd(n,k)) \tag{2}$$
It has been ...
- 1,183
6
votes
1
answer
761
views
Checking if one polytope is contained in another
I have two sets of inequalities, say, $Ax \leq 0$ and $Bx \leq 0$. I would like to know if they both define the same polytope. Or, even, whether one is contained in the other.
At the moment I am ...
- 491
5
votes
0
answers
343
views
Duality between K-theory and K-homology in the non-compact, spin$^c$ case
Let $M$ be a compact spin$^c$ manifold, so that it has a fundamental class $[M] \in K_n(M)$. It is well-known that the cap product with $[M]$ induces Poincare duality isomorphisms $K^\ast(M) \cong K_\...
- 2,998
4
votes
1
answer
456
views
Which topological spaces admit embeddings into Euclidean spaces
I'm interested in the dual question to:
continuous images of open intervals, about surjections onto open intervals.
Namely, if $X$ is a topological space, when can we guarantee that there exists a ...
- 5,405
4
votes
2
answers
483
views
Is every closed subspace of the Schwartz space densely embedded into its dual space?
My original question is from this ME post but I think I need a broader understanding for this.
The Schwartz space $\mathcal{S}$ and its subspaces are examples of nuclear spaces. In fact, any closed ...
- 3,477
4
votes
1
answer
891
views
Basic result in semi-infinite linear programming
Consider a standard linear program of the form $$\textrm{minimize}_x~~~~ c^Tx~~~~ s.t. \\ Ax = b \\ x \geq 0$$ with $x\in \mathbb{R}^n$ and $A \in \mathbb{R}^{m \times n}$. It is well known that, if ...
- 4,049
4
votes
2
answers
2k
views
Simplified knapsack problem
There is a problem that I can not solve.
Given a set of items (each item has some integer weight) we have to fill bag with some number of copies of these items, with the only restriction that the ...
- 41
4
votes
1
answer
222
views
$\ast$-autonomous categories with non-invertible dualizing object?
1. Definition
Firstly, recall the following nLab-definition of a $\ast$-autonomous category:
A $\ast$-autonomous category is a symmetric closed monoidal category $(C,\otimes,I,\multimap)$ with a ...
- 764
4
votes
1
answer
204
views
Reference: Packing under translation is in NP
I am looking for a reference for a result that I am aware of.
Let me describe the result.
Given a polygon $C$ and polygons $p_1,\ldots,p_n$, it can be decided in NP
time, if $p_1,\ldots,p_n$ can be ...
- 479
3
votes
2
answers
128
views
Duals and sub-objects in a monoidal category
Consider $\mathcal{M}$ a monoidal category. Let $V$ be an object that admits a left/right dual. If $U$ is a subject of $V$ then does it also admit a left right dual?
3
votes
4
answers
4k
views
Existence of nonnegative solutions to an underdetermined system of linear equations
Similar questions have been asked elsewhere, but I think this is sufficiently different to warrant a new post. I have a particular matrix $A$ and would like to know when the system $Ax = 0$ has at ...
- 491
3
votes
2
answers
792
views
complexity of finding optimal matchings of given fixed size
It is known, that maximal matchings (i.e. matchings with the maximal number of edges) and optimal matchings (i.e. matchings for which the sum of edge weights is optimal) can be calculated in ...
- 13.2k