User aelguindy - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-19T22:39:24Z http://mathoverflow.net/feeds/user/20532 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/126621/matrix-where-every-subset-of-rows-has-maximal-rank Matrix where every subset of rows has maximal rank aelguindy 2013-04-05T13:31:57Z 2013-04-05T13:57:40Z <p>I am looking for a class of matrices $M(n(m), m, k(m), \phi)$ with the following properties:</p> <ol> <li>M is $n \times m$ where $n(m) > m$.</li> <li>Every subset of rows of size $k$ has (maximal) rank $m$.</li> <li>$n(m)$ grows slowly.</li> <li>$m \leq k(m) \leq (1 - \phi) n(m)$ and $k(m)$ is as close as possible to $m$.</li> </ol> <p>and preferably, the matrix is binary.</p> <p>Has this been studied before? I appreciate any pointers.</p> <p>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$).</p> <p>Also, any probabilistic suggestions that perform better than the uniform random binary matrix are welcome.</p> <p>(I apologize if my question turns out to be elementary, I also appreciate any help with properly tagging the question.)</p> http://mathoverflow.net/questions/99813/probability-that-random-weights-on-k-n-satisfy-triangle-inequality Probability that random weights on $K_n$ satisfy triangle inequality aelguindy 2012-06-17T00:47:31Z 2012-06-19T04:53:55Z <p>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]$?</p> <p>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.</p> <p>Notes:</p> <ol> <li>This question was posted on math.SE <a href="http://math.stackexchange.com/questions/158233/probability-that-a-random-weight-function-on-k-n-satisfies-the-triangle-inequa" rel="nofollow">here</a>. I got no answers and it seems pretty inactive at the moment.</li> <li>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.</li> </ol> http://mathoverflow.net/questions/126621/matrix-where-every-subset-of-rows-has-maximal-rank Comment by aelguindy aelguindy 2013-04-08T12:12:03Z 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.. http://mathoverflow.net/questions/99813/probability-that-random-weights-on-k-n-satisfy-triangle-inequality/99814#99814 Comment by aelguindy aelguindy 2012-06-18T16:16:38Z 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.