User aelguindy - MathOverflow

Matrix where every subset of rows has maximal rank

2013-04-05T13:31:57Z

I am looking for a class of matrices $M(n(m), m, k(m), \phi)$ with the following properties:

M is $n \times m$ where $n(m) > m$.
Every subset of rows of size $k$ has (maximal) rank $m$.
$n(m)$ grows slowly.
$m \leq k(m) \leq (1 - \phi) n(m)$ and $k(m)$ is as close as possible to $m$.

and preferably, the matrix is binary.

Has this been studied before? I appreciate any pointers.

I know that a random uniform binary matrix with $n(m) \approx \frac{2}{1-\phi}(m + log 1/\delta)$ and $k(m) = m$ satisfies the properties above with probability $1 - \delta$ (for large enough $m$).

Also, any probabilistic suggestions that perform better than the uniform random binary matrix are welcome.

(I apologize if my question turns out to be elementary, I also appreciate any help with properly tagging the question.)

Probability that random weights on $K_n$ satisfy triangle inequality

2012-06-17T00:47:31Z

Given $K_n$, if a random real weight between $[0, 1]$ is chosen for every edge, what is the probability that the graph satisfies the triangle inequality? How about the discrete version, where the weights are integers in $[0, k]$?

It is easy to see that if $n = 3$ the probability is $1/2$ and (empirically) that the probability approaches zero as n goes to $\infty$. Has anyone studied the problem before? Any exact or asymptotic results are appreciated.

Notes:

This question was posted on math.SE here. I got no answers and it seems pretty inactive at the moment.
This is my first question on mathoverflow, so I am sorry if this is not research-level, but it seems to me that it is.

Comment by aelguindy

2013-04-08T12:12:03Z

@ChrisGodsil Thanks! I am looking into MDS codes, and while it seems that they are not exactly what I want they are giving pointers to some useful leads.. @JyrkiLahtonen if I am not mistaken, fountain codes are using random matrices. What I refer to in the question is in fact one simplistic form of fountain codes (simplified Luby transform). I am primarily looking for something deterministic. Better fountain codes use different distributions to improve encoding/decoding efficiency..

Comment by aelguindy

2012-06-18T16:16:38Z

I guess that's as good as it gets, an exact result is probably very difficult. I will try to refine and tighten the bounds as much as I can.