All Questions
2,253 questions
-2
votes
1
answer
470
views
Little conjecture about sums of reciprocals
Given a finite list $x_i$ of $N$ positive reals, it seems that $\sum_{i=1}^N x_i = \sum_{i=1}^N x_i {}^{-1} \Rightarrow \sum_{i=1}^N x_i \geq N$. Can anyone give me a proof?
- 2,513
1
vote
1
answer
9k
views
what is the difference between the revised simplex method andthe full tableu?
No to sound naive but they look like they include the same steps to me, one's just the algorithmical representation of the other. Thanks in advance.
- 111
9
votes
5
answers
1k
views
estimate the error term in CLT
Let $X_m = \frac{1}{\sqrt{m}}\sum_{k=1}^m Z_k$ where $Z_k$ are iid equally likely on $\{\pm 1\}$. Then $X_m$ convergens to $X \sim \mathcal{N}(0,1)$ in distribution by CLT.
Let $f$ be a smooth ...
- 1,839
2
votes
0
answers
281
views
Recovering a piecewise affine function
Lets say I have an piecewise affine convex function $f(x_1,x_2)$, on which the following operations are possible:
Computing $f(x_1,x_2)$.
Computing a subgradient to $f$ at $(x_1,x_2)$
Computing all ...
- 567
20
votes
6
answers
6k
views
subadditive implies concave
Let $f:R_+\to R_+$ be smooth on $(0,\infty)$, increasing, $f(0)=0$ and
$\lim_{x\to\infty}=\infty$. Assume also that $f$ is subadditive:
$f(x+y)\le f(x)+f(y)$ for all $x,y\ge 0$. Must $f$ be concave? ...
- 213
2
votes
1
answer
178
views
Maximal inequality over two indices
In Freedman's series of 3 books on Markov processes, I find that I keep on running into terms like:
P[$\max_{0 \leq s \leq 1, s \leq t \leq rs}$ | B(t) - B(s) | > $\epsilon$]
in the background of ...
2
votes
2
answers
640
views
Sorting a binary matrix diagonal in polynomial time while preserving rows
Is there a polynomial time solution to sort an arbitrary binary square matrix in polynomial time by rows so that the diagonal contains a 1 if any row contains a 1 in that column?
For example given ...
- 121
0
votes
1
answer
1k
views
For Ax = b, x and b unknown vectors, how do I solve the x that maximizes min(b_i)?
Given a matrix $A$, each element $A_{i,j} \geq 0$, find the vector $\vec x$ that maximizes the minimum element in $\vec b$ ($\vec b = A \vec x$). Note that this is not a linear equation system as I ...
- 135
2
votes
1
answer
1k
views
Inequality concerning absolute value of a polynomial
Let
$$f(z) = (1-1/t) z^w + z/t - 1$$
with integers $t\geq2$ and $w\geq2$.Let $r=1+1/(tw^3)$. How do I show
$$\left\lvert f(r e^{i\varphi}) \right\rvert \geq \left\lvert f(r) \right\rvert$$
for any $\...
- 577
3
votes
1
answer
1k
views
Proving inequalities over algebraic structures
I've been looking at proof techniques in formal systems like Coq and Agda recently, and encountered the newring tactic described here for proving equalities over ...
- 177
3
votes
1
answer
474
views
Analogues of the Golden-Thompson inequality
Are there any analogues of the Golden-Thompson Inequality for moment generating functions? The Golden-Thompson Inequality asserts the following: If $A$ and $B$ are two $n \times n$ Hermitian matrices, ...
- 31
6
votes
1
answer
369
views
Denominators in the solution to Hilbert's XVII
Hilbert's seventeenth problem asks to prove that every positive semidefinite form can be written as the sum of squares of rational functions. Currently we don't seem to have a good understanding of ...
- 85.6k
5
votes
2
answers
3k
views
Continuous Linear Programming: Estimating a Solution
I have a "continuous" linear programming problem that involves maximizing a linear function over a curved convex space. In typical LP problems, the convex space is a polytope, but in this case the ...
- 373
4
votes
1
answer
275
views
Symmetry of the integer gap
Are there results that bound the asymmetry of the duality gap of an integer program? That is to say, if the difference between the LP solution and the IP (primal) solution is $a$, is there a function ...
- 183
5
votes
2
answers
1k
views
Inequality involving probability measures [closed]
I have been working on a problem(alternate minimization) where I want to establish an inequality in which I am stuck.
An $\alpha$- parameterized version of the divergence(Kullback-Leibler) takes the ...
- 779
3
votes
2
answers
489
views
Positivity of a finite sum
Let $i$, $k$ be integers such that $2 \leq i \leq k$. I would like to show that the sum
$$
\sum_{j=1}^{i-1} \frac{(-1)^{j-1}(i-j)^k}{(i-j)! (j-1)!}
$$
is positive. I have carried out extensive ...
- 3,142
12
votes
2
answers
1k
views
Positivity of sequences via generating series
There are different ways of showing that a given sequence $a_0,a_1,a_2,\dots$
of integers, say, is nonnegative. For example, one can show that $a_n$ count
something, or express $a_n$ as a (multiple) ...
- 13.5k
5
votes
2
answers
1k
views
Applications of minmax theorem(s)
Intro We suppose $X$ and $Y$ are nonempty sets and f: $X\times Y \rightarrow \mathbb{R}$. A minimax theorem is a theorem that asserts that, under certain conditions,
$$ \inf_Y \sup_X f = \sup_X \...
1
vote
3
answers
2k
views
How to solve Linear Programming problem with tighter Integer Programming constraints
I want to learn a bit about Linear Programming.
After some research, I decided to solve the Cutting Stock problem as an example to learn. After doing some more research, I feel like I finally ...
9
votes
1
answer
6k
views
Proving that a binary matrix is totally unimodular
I'm working on a set of problems for which I can formulate binary integer programs. When I solve the linear relaxations of these problems, I always get integer solutions. I would like to prove that ...
- 213
2
votes
1
answer
803
views
Inequality constraints, probability distributions, and integer partitions
I am interested in the possibility of generating probability distributions using inequality constraints. For instance assume that we have three urns with total of a 10 balls. Thus,
$a + b + c = 10$
...
10
votes
3
answers
6k
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 ...
- 7,857
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 $...
5
votes
1
answer
429
views
A plausible positivity
After getting stuck with the
previous positivity
(it probably sounds too complex),
I would like to give a version of the problem which is of most interest to me.
Consider a sequence of real numbers
$...
- 13.5k
6
votes
1
answer
354
views
Positivity of "harmonic" summation
The settings for the problem are as follows. Given
a real number $\alpha\in[0,1]$, consider
a sequence of real (positive, negative and zero) numbers
$a_1,a_2,\dots,a_n,\dots$ satisfying
(1) $a_1=1$,
...
- 13.5k
8
votes
1
answer
1k
views
Salem Inequality
I have come across this inequality in the paper "Local estimates for exponential polynomials and their applications to inequalities of the uncertainty principle type" http://www.math.msu.edu/~fedja/...
- 1,795
152
votes
18
answers
24k
views
Why do we care about $L^p$ spaces besides $p = 1$, $p = 2$, and $p = \infty$?
I was helping a student study for a functional analysis exam and the question came up as to when, in practice, one needs to consider the Banach space $L^p$ for some value of $p$ other than the obvious ...
4
votes
1
answer
866
views
When is a triangular matrix totally unimodular?
I have a {0,1}, invertible, triangular matrix, that I would like to show is totally unimodular. Are there any known results on the total unimodularity of classes of triangular matrices?
- 1,182
5
votes
1
answer
271
views
Feasibility of linear programs
It's known that finding the intersection of n halfplanes in 2-d takes $\Omega(n\log n)$ time. Does the lower bound apply if we change the question to deciding whether the intersection is non-empty?
- 201
2
votes
0
answers
5k
views
A system of linear equations with linear constraints
Mathematical problem.
Suppose we have $2n$ indeterminates $x_1,\dots,x_n$ and $y_1,\dots,y_n$ (which are denoted by $q$ with indices and called abundances below) and $m$ subsets $P_1,\dots,P_m$ of $\...
4
votes
0
answers
790
views
Is it possible to use linear programming to solve this problem?
I am trying to write software to minimize pricing for cell phone subscription services, ie: choose the optimum plan for each customer in a large group.
Could someone comment on whether this is ...
- 41
4
votes
2
answers
711
views
Another plausible inequality.
I come across the following problem in my study.
Consider in the real field. Let $ 0\le x\le1 $, $a_1^2+a_2^2=b_1^2+b_2^2=1$.Is it true
$ (a_1b_1+xa_2b_2)^2\le\left(\frac{(1-x)+(1+x)(a_1b_1+a_2b_2)}...
- 1,858
0
votes
2
answers
579
views
Linear algebra inequality
I'm wondering (hoping) if an inequality is true. Please can anyone help me?
Let $V$ be a complex vector space $dim_{\mathbb{C}}(V)=n$
with a hermitian scalar product $h$.
Let $v,a, b \in V$.
Is it ...
- 1,727
2
votes
3
answers
806
views
An Linear Algebra Inequality
How to prove the following inequality:
Let $X$ and $Y$ be $n\times m$ matrices with real entries. Prove that
\begin{equation}
\det\left(XY^T\right)^2 \leq \det\left(XX^T\right)\det\left(YY^T\right) .
\...
- 31
6
votes
3
answers
2k
views
A simple infinite dimensional optimization problem
I'd be grateful for a reference for the following result, which I believe to be true, and
should be well-known.
Let the continuous functions $f_0,f_1,\cdots,f_n: [0,1]\rightarrow [0,\infty)$ be ...
- 520
3
votes
2
answers
1k
views
Cyclic order relation in Zn
The ring Zn:={0,1,..,n-1} under addition and multiplication modulo n.
Suppose a,b,c,x $\in$ Zn are nonzero and the cyclic order R(a,b,c) holds, then under what conditions does R(ax,bx,cx) hold ?
- 1,190
2
votes
1
answer
739
views
Another mixed mean inequality
Let $a_1,$ $a_2,$ $\ldots,$ $a_n$ be positive real numbers. Prove that
$$\sqrt{\frac{a_1^2+\left( \frac{a_1+a_2}{2}\right)^2+\cdots +\left(\frac{a_1+a_2+\cdots +a_n}{n}\right)^2}{n}} \le \frac{a_1+\...
- 81
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
27
votes
2
answers
2k
views
How often are irrational numbers well-approximated by rationals?
Suppose $x\in \mathbb{R}$ is irrational, with irrationality measure $\mu=\mu(x)$; this means that the inequality $|x-\frac{p}{q}|< q^{-\lambda}$ has infinitely many solutions in integers $p,q$ if ...
- 13.1k
1
vote
0
answers
1k
views
Covariance matrix formula interpretation - what am I missing?
I'm reading a paper that outlines the calculation of a covariance matrix like the following:
$C=\displaystyle\sum^{N_b}_{i=1}\vec{x}_i\vec{x}_i^T$
What is the order of this matrix? My interpretation ...
- 111
0
votes
2
answers
4k
views
Linear programming piecewise linear objective
I am fairly new at linear programming/optimization and am currently working on implementing a linear program that is stated like this:
max $\sum_{i=1}^{k}{p(\vec \alpha \cdot \vec c_i)}$
$s.t. $
$|\...
- 3
1
vote
3
answers
379
views
monotonicity from 4 term-recursion.
In determining the monotonicity of coefficients in a series expansion (which appeared in one of my study), I come across the following problem.
Let $p\ge 2$ be an integer, and $$6p^3(i+3)d_{i+3}=6p^...
- 1,858
4
votes
2
answers
1k
views
Upper bound for a+b+c in terms of ab+bc+ac
I am given a triple of positive integers $a,b,c$ such that $a \geq 1$ and $b,c \geq 2$.
I would like to find an upper bound for $a+b+c$ in terms of $n = ab+bc+ac$. Clearly $a+b+c < ab+bc+ac = n$.
...
- 3,463
10
votes
1
answer
2k
views
Sum of difference moduli vs. sum of modulus differences
This is a failed attempt of mine at creating a contest problem; the failure is in the fact that I wasn't able to solve it myself.
Let $x_1$, $x_2$, ..., $x_n$ be $n$ reals. For any integer $k$, ...
- 33.8k
8
votes
5
answers
2k
views
A plausible inequality
I come across the following problem in my study.
Let $x_i, y_i\in \mathbb{R}, i=1,2,\cdots,n$ with $\sum\limits_{i=1}^nx_i^2=\sum\limits_{i=1}^ny_i^2=1$, and $a_1\ge a_2\ge \cdots \ge a_n>0 $. Is ...
- 1,858
62
votes
7
answers
26k
views
Is the Jaccard distance a distance?
Wikipedia defines the Jaccard distance between sets A and B as $$J_\delta(A,B)=1-\frac{|A\cap B|}{|A\cup B|}.$$ There's also a book claiming that this is a metric. However, I couldn't find any ...
- 1,355
7
votes
8
answers
2k
views
Examples of inequality implied by equality.
It is well known Cauchy's inequality is implied by Lagrange's identity. Bohr's inequality $|a -b|^2 \le p|a|^2 +q|b|^2$, where $\frac{1}{p}+\frac{1}{q}=1$, is implied by $|a -b|^2 +|\sqrt{p/q}a+\sqrt{...
29
votes
8
answers
6k
views
Is there a good reason why $a^{2b} + b^{2a} \le 1$ when $a+b=1$?
The following problem is not from me, yet I find it a big challenge to give a nice (in contrast to 'heavy computation') proof. The motivation for me to post it lies in its concise content.
If $a$ and ...
- 1,858
14
votes
2
answers
16k
views
When is the product of a set of numbers greater than the sum of them?
This could well be too general a question, but I'd be interested in solutions to special cases too. Say you have some finite set of positive real numbers $x_i$, when is it the case that $\sum_i x_i &...
- 367
21
votes
1
answer
2k
views
Is there a combinatorial proof of Cauchy-Schwarz?
I've only played with this a little for the past day or so, and haven't thought about it too hard, so it might be obvious. Obviously it's not fair to ask for a "combinatorial proof" of an inequality ...
- 12.6k