Is there a way to compute minimum distance of a code given a systematic parity check matrix? I know that min dist is smallest number $d$ such that there exists $d$ linearly dependant columns. I am looking in particular to find minimum distance of binary (codes over $\mathbb{F}_{2^l}$) quasi-cyclic  of rate q/q+1. Parity check matrix for such codes have a structure $H=[I|C_1|C_2|...|C_m]$ where each $C_¡$ is a from class of circulant matrices. It may be useful that one can treat these codes as modules. Or even if there are any approximate algoruihms for this ?
123545
Is there a way to compute minimum distance of a code given a systematic parity check matrix? I know that min dist is smallest number $d$ such that there exists $d$ linearly dependant columns. I am looking in particular to find minimum distance of binary (codes over $\mathbb{F}_{2^l}$) quasi-cyclic  of rate q/q+1. Parity check matrix for such codes have a structure $H=[I|C_1|C_2|...|C_m]$ where each $C_¡$ is a from class of circulant matrices. It may be useful that one can treat these codes as modules. Or even if there are any approximate algoruihms for this ?
14798
How to prove $\text{Rank}(AB)\leq \min(\text{Rank}(A), \text{Rank}(B))$?
105796
It is known that for $\Theta(1)$ error the worst case definition of randomized communication complexity and average case definition are equivalent. But when the error is $0$, the worst case randomized communication complexity is same as deterministic communication complexity.  Is any function known to have super-constant deterministic communication complexity but constant zero error randomized communication complexity?  More generally, what is a witness function that separates deterministic communication complexity and zero-error randomized communication complexity?  Any help is appreciated.
78622
Define $A_i$ as the number of words in binary Hamming code of weight $i$. Prove:   $$A_1=0, A_0=1$$   $$(i+1)A_{i+1}+A_i+(n-i+1)A_{i-1}= {n \choose i}$$   I am a tad clueless as to how to proceed. I can show that for a given weight $i$, the number of columns of such weight of the parity-check matrix $H$ are precisely $n\choose i$. Every codeword $c$ of Ham must hold $c*H^t$. Furthermore, I can describe the generating matrix $G$ as being a matrix of the form [$A|I_{n-r}$], where there are $n\choose i$ rows in $A$ of weight $i$, for $2\le i \le n$.  I am certain the proof has to do with these two properties, yet I am unable to connect the points. Perhaps a proof with induction could be of use?  Any hints/direction towards the right way and what I should be looking at or focusing on will be extremely appreciated!
913
Suppose $a_1, a_2,\dots , a_n$ are $n$ positive real numbers with $a_1a_2 \dots a_n = 1$.   Then what is the minimum value of $(1 + a_1)(1 + a_2). . .(1 + a_n)$ ?    I think $(1 + a_1)(1 + a_2). . .(1 + a_n)$ takes its minimum value when $a_1=a_2=\dots=a_n=1$ and thus the minimum value is $2^n$.  I don't know how to prove it. Please help.
91087
How to show that the relationship $\left | \lambda_{min} \right | \geq \sigma_{min}$ holds between the minimum eigenvalue and singular value of a square matrix $A \in \mathbb{C}^{n \times n}$?
28990
I have a (symmetric) matrix M that represents the distance between each pair of nodes. For example,       A   B   C   D   E   F   G   H   I   J   K   L A   0  20  20  20  40  60  60  60 100 120 120 120 B  20   0  20  20  60  80  80  80 120 140 140 140 C  20  20   0  20  60  80  80  80 120 140 140 140 D  20  20  20   0  60  80  80  80 120 140 140 140 E  40  60  60  60   0  20  20  20  60  80  80  80 F  60  80  80  80  20   0  20  20  40  60  60  60 G  60  80  80  80  20  20   0  20  60  80  80  80 H  60  80  80  80  20  20  20   0  60  80  80  80 I 100 120 120 120  60  40  60  60   0  20  20  20 J 120 140 140 140  80  60  80  80  20   0  20  20 K 120 140 140 140  80  60  80  80  20  20   0  20 L 120 140 140 140  80  60  80  80  20  20  20   0   Is there any method to extract clusters from M (if needed, the number of clusters can be fixed), such that each cluster contains nodes with small distances between them. In the example, the clusters would be (A, B, C, D), (E, F, G, H) and (I, J, K, L).  I've already tried UPGMA and k-means but the resulting clusters are very bad.  The distances are the average steps a random walker would take to go from node A to node B (!= A) and go back to node A. It's guaranteed that M^1/2 is a metric. To run k-means, I don't use the centroid. I define the distance between node n cluster c as the average distance between n and all nodes in c.  Thanks a lot :)
24426
It is a theorem that, for every finite group $G$, there exists an $n$ such that $G \leq  S_n$. Given a particular group, is there any way to determine or bound the smallest $n$ such that this occurs? The representation of the group is up to you, though bounds that use less information are preferred.  If this problem is too hard, specific special cases are also interesting, as are bounds on $n$.
102230
I am calculating the class group of $\mathbb Q(\sqrt 6)$. My working is as follows:  The Minkowski bound is $\lambda(6)=\sqrt 6&lt;3$ so we only need to look at prime ideals of norm $2$. $2$ divides the discriminant, $24$, of $\mathbb Q(\sqrt 6)$, so $2$ ramifies, and so for any prime ideal $\mathfrak p$ of norm $2$, $\mathfrak p^2$ is principal. But $(2, \sqrt 6)^2=(2)$, so $\mathfrak p=(2, \sqrt 6)$ has norm $2$. If I can show $\mathfrak p$ is not principal, then I can conclude that $Cl(\mathbb Q(\sqrt 6))\cong C_2.$ But if there was an element of $\mathcal O_{\mathbb Q(\sqrt 6)}$ of norm 2, this would correspond to a solution of the diophantine equation $x^2-6y^2=2$. Clearly $x$ is even, so writing $x=2n$ we get $2n^2-3y^2=1$. Now reducing modulo $3$, we get $2n^2\equiv 1 \pmod 3$ which has no soultions. Hence $\mathfrak p$ is not principal and $Cl (\mathbb Q(\sqrt 6)) \cong C_2.$  However,  says that the class group is trivial. Where have I gone wrong? What am I misunderstanding? Is $(2, \sqrt 6)$ principal?
106918
What is the most efficient way to cacluate the closest power of a 2 or 10 to another number? e.g.  3.5 would return 4 for power of 2 and 1 for power of 10  123 would return 128 for power of 2 and 100 for power of 10  0.24 would return 0.25 for power of 2 and 0.1 for power of 10  I'm just looking for the algorithm and don't mind the language.
75934
Why and how is the  of a matrix in $M_3(\mathbb C)$ fully determined by its characteristic and minimal polynomials? And why does it fail for $n &gt;3$?   Thanks.
114818
I was wondering if anyone had any insight or information on how one might go about determining point coordinates in an n-dimensional space from point pair distances.  For example, say I start with a table of pairwise Euclidean distances between points for 10 points $\{a, \ldots, j\}$.  This would have a distance for each distinct pair of points, a through j, so 45 separate distances.  I want to be able to produce an n-dimensional vector for each point so that the Euclidean distance between each of the points matches the point pair distances from my original table.  Any insight on the subject would be much appreciated.
97323
Let L1 be the line passing through the point $P_1=(−11, 10, −1)$ with direction vector $\vec d_1=\begin{bmatrix}−2\\ 3\\ −1\end{bmatrix}t$, and let $L_2$ be the line passing through the point $P_2=(−8, 9, 10)$ with direction vector $\vec d_2=\begin{bmatrix}−1\\ 3\\1\end{bmatrix}t$. Find the shortest distance, $d$, between these two lines, and find a point $Q_1$ on $L_1$ and a point $Q_2$ on $L_2$ so that $d(Q_1,Q_2) = d$.   I dont really understand how to properly approach this question, how do i start?
85204
In  vzn asked about the following problem, which I'll call Vector-Subset-Sum.     Given a set of vectors $v_i$ over GF(2) and a target vector $y$, is there a subset of the $v_i$ summing to $y$?   In the answers, comments, and referenced papers I noted   The decision problem is in P. The natural minimization problem (finding the smallest subset) is NP-hard. It's related to the problem of finding sparse codewords in a linear code.   My question is: are there any known polynomial-time approximation algorithms for the minimization problem in (2)? I know very little about coding theory, so there may be some obvious or well-known approximation-preserving reductions to (3) that I have not seen.
52341
I'm trying to find an efficient algorithm for the following problem:  Given two different sets, both of size $N$. Each element in the two sets has coordinates $(x,y)$. The task is to optimize the pairings between these two sets such that the maximum distance between the paired elements given a pairing, is minimized. I have only found algorithms that deal with the squared sum of all distances between paired elements or the smallest distance between any two points from the two different sets.  For example: Given a list of $N$ pair of points that are associated with locations $(x_0,y_0), (x_1,y_1), (x_2,y_2),\dotsc,( x_{n-1},y_{n-1})$, name them $a_0,a_1,a_2,\dotsc,a_{N-1}$ accordingly. And another list of $N$ pairs of different points (locations) $(x_0,y_0), (x_1,y_1), (x_2,y_2),\dotsc,( x_{n-1},y_{n-1})$, name them $b_0,b_1,b_2,\dotsc,b_{N-1}$ accordingly. How can I pair all elements (each element is a pair of points) from list 1 $(a_0,a_1,a_2\dotsc,a_{N-1})$ to the other elements in list 2 $(b_0,b_1,b_2,\dotsc,b_{N-1})$ so that we chose the shortest distances? eventually, I'd need to print the maximum distance among all minimum distances (that we have found for each of the elements). Any idea how can this be achieved in reasonable run time? or name an algorithm that might help here.
56397
Prove that the order of an element in $S_n$ equals the least common multiple of the lengths of the cycles in its cycle decomposition.  Proof: Let $\sigma \in S_n$. Then $\sigma = (a_1a_2...a_{m_1})(a_{m_1+1}a_{m_1+2}...a_{m_2})....(a_{m_{k-1}+1}a_{m_{k-1}+2}...a_{m_{k}})$ represents the cycle decomposition of $\sigma$. Suppose $|\sigma| = n$ is the order of an element in $S_n$. So $\sigma^n = 1$. Can someone please help  me?  I don't know how if I am doing this fine. And I am stuck. Thank you for any help.
92200
What's the best algorithm that takes in two positive integers $a,b$   and returns a positive integer $c$, such that all $c$'s are unique and   $(a,b)$ is distinguishable from $(b,a)$; where the best means that the   length of $c$ in terms of digits is shortest possible, on average?      This implies that we can work out $a,b$ from $c$ with the same algorithm. (reversing it)   If we have a bound $x$ such that $a,b\le x$, then $f(a,b)$ has $x^2$ unique values which means our $c$ needs to take values from $[1,x^2]$ to have the least amount of digits, which can be achieved with the following function:  $$f(a,b)=(a-1)x+b$$  If $x$ does not exist, what's the optimal algorithm then?   (To make sense which algorithm is the shortest, I was comparing the length of the $c$ with the sum of lengths of $a,b$ and calculating the average which is more precise the more values we consider.)    I had two ideas so far;   $(1)$ Factorization  Take the factors of $a$ and $b$. Now you can use the second longest sequence of $0$s as a separator between factors, and the longest sequence of $0$s as a separator between the factors of the two numbers.   Example: $f(123,1007)=(3\times41 ),( 19\times53)=30410019053$  Example: $f(30,1006)=(2\times3\times5),(2\times503)=2003005000200503$  But this can be optimized, for cases such as $f(2^{64},3^{64})$, and even then, seems like it is too much extra digits.   $(2)$ Trailing zeroes  Take $a$, reverse its digits and put a random digit in front of the first digit. That way, the result does not have trailing zeroes. Then use the longest sequence of $0$s as a separator from $b$.   Example: $f(123,456)=93210456$  Example: $f(123,10100)=932100010100$  Example: $f(420,314)=902400314$  This also has room for optimization if we look at individual cases and add more specific rules. But it feels like it won't be optimal even then.   I suppose the optimal solution would need to look at couple or more cases individually?