Tagged Questions

10
votes
0answers
82 views

Combinatorics in finite vector space

Let $q$ be a prime power and $V$ a finite $\mathbb F_q$-vector space with two subspaces $I$ and $J$. Let $k$, $a$ and $b$ be non-negative integers. Determine the number of subspaces $K$ of $V$ ...
1
vote
1answer
34 views

Godsil & Royle, Theorem 9.5.1: Extension for digraphs?

I was wondering if there is an extension to digraphs for Theorem 9.5.1 in Godsil & Royle's Algebraic Graph Theory. The Theorem can also be found in Willem Haemers paper Interlacing Eigenvalues ...
10
votes
2answers
154 views

Choosing a linear map $(\mathbb{Z}/2\mathbb{Z})^n \rightarrow \mathbb{Z}/2\mathbb{Z}$ which is nonzero on half of a sequence of vectors

Let $v_1,\ldots,v_m \in (\mathbb{Z}/2\mathbb{Z})^n$ be nonzero vectors. Is it always possible to choose a linear map $f : (\mathbb{Z}/2\mathbb{Z})^n \rightarrow \mathbb{Z}/2\mathbb{Z}$ such that $f$ ...
4
votes
0answers
25 views

Isomorphism between $E_8$ lattice and lattice defined by Extended Hamming Code

I have read that the following two lattices are isomorphic, and of course it seems believable, but it would be nice to have a sketch of how to construct the bijection. Let $C$ be some extended ...
2
votes
0answers
101 views

Can a linear combination of even Legendre polynomials have common real root(s) with a linear combination of odd Legendre polynomials?

I am using the following definition of Legendre Polynomials: $P_0(x)=1$, $P_1(x)=x$ and $$P_{k+1}(x)=\left(\frac{2k+1}{k+1}\right)xP_k(x)−\left(\frac{k}{k+1}\right)P_{k−1}(x)$$ Let ...
1
vote
1answer
54 views

Combinatorial identity. Using echelon matrices.

Determine the exponents $e_i$ s.t. the following identity is correct. $$\sum\limits_{i=0}^k q^{e_i} {\binom mi}_q {\binom{n}{k-i}}_q = {\binom{n+m}{k}}_q$$ Note: When $q=1$ the equation reduces to a ...
4
votes
0answers
57 views

Linear Independence Game

Suppose you have a set $X$ of vectors in $\mathbb{F}_2^n$, with $|X| \ge n+1$, and consider the following game. On their turn, each player (2 player game) chooses from $X$ one vector and sets it aside ...
4
votes
2answers
70 views

Minimum distance of a binary linear code

I need to find parameters $n$, $k$ and $d$ of a binary linear code from its Generator Matrix. How can I find parameter $d$ efficiently? I know the method that compute all the codewords and take ...
2
votes
0answers
29 views

When does a simplex have an interior lattice point?

Given $r$ vectors $v_1, \dots, v_r$ in $\mathbb{Z}^n$, is there an easy way (in terms of the entries of the $v_i$) to determine if there is a point of $\mathbb{Z}^n$ in the interior of the simplex ...
3
votes
3answers
37 views

how many linear transformation like $T$ are from $V_F$ to $V_F$ such that $W=\ imT$ or$W=\ kerT$? ($V_F$and $F$ is finite )

let $V_F$ be finite vector space and $W$ is subspace of $V_F$ and $F$ is finite now how many linear transformation like $T$ are from $V_F$ to $V_F$( $T:V_F \to V_F)$ such that $W=\ imT$ and how ...
0
votes
1answer
64 views

Prove $MM^t=A+kI$ for matrices associated to graphs

How can I prove that $MM^t=A+kI$ for incidence matrix $M$ and adjacency matrix $A$ of a $k$-regular graph with $n$ vertices? It is easy to see that $MM^t$ is an $n\times n$-matrix (like $A$), ...
3
votes
3answers
366 views

Finding the parity check matrix for $(15, 11)$ Hamming Codes

I understand how Hamming Codes and their error detection works, but I'm confused how the parity check matrix is found. How exactly is this computed?
1
vote
2answers
61 views

Prove an inequality in a group ring

Let $$G=\bigoplus_{n\in\mathbb{Z}}\left(\mathbb{Z}/2\mathbb{Z}\right)_n$$ be a group, and for any $n\in \mathbb{Z}$, denote $\delta_n$ to be the element in $G$ with $n$-th coordinate $1$ and zero at ...
2
votes
1answer
37 views

What is the probability that a random sparse vector lies in a subspace?

Let $\mathbb{F}$ be a Finite Field. For $m\leq n$ a vector $v$ in $\mathbb{F}^n$ is $m$-sparse if $ \sum_i (v_i \neq 0) \leq m$, i.e. , the hamming weight is almost m. Let we call $S(n,m)$ the set of ...
1
vote
1answer
70 views

What is a relationship between sets and Trinomial Coefficient?

We know that the relationship between set with n Cardinality named A and Binomial Coefficient is all about subsets of the set A with n Cardinality. Binomial Coefficients describes Cardinality of ...
1
vote
0answers
35 views

Relation between the coefficients in the different basis.

Let $f: \mathbb{R} \rightarrow \mathbb{R}$ we can represent this polynomial $f$ in two basis, Monomial basis and hermite basis. How can we get the relationship between coefficients of $f$ in both ...
4
votes
2answers
77 views

Arf invariant for quadratic forms

I am reading a paper in which they define the Arf invariant as follows: Let $V$ be a vector space of dimension $2n$ over $\mathbb{Z}_2$ and $f$ is a non-degenerate bilinear form $V$. We call $q$ a ...
-2
votes
1answer
54 views

What will be total number of solutions of $n_1a+n_2b+n_3c=n$?

What will be total number of solutions of $n_1a+n_2b+n_3c=n$? Here, $n_1,n_2,n_3,n$ are constants already provided in the question and $a,b,c$ are variables. What we have to do is find out the total ...
2
votes
0answers
71 views

Sorting combinations of linearly independent vectors

Given a set of $m$ vectors in $\mathbb{R}^n$ ($m > n$), sort all combinations of $n$ linearly independent vectors according to the determinant of the matrix whose columns are the $n$ vectors. ...
7
votes
1answer
111 views

Probability that a $3\times 3$ matrix with entries in $\{0,1,2,3\}$ is invertible.

Let $A$ be a $3\times 3$ matrix, and each of its entries takes value from $\{0, 1, 2, 3\}$ with probability $1/4$ for each value. What is the probability that A is invertible? I have tried to list ...
1
vote
1answer
45 views

A Combinatorial Question to Solve a System of Equations [duplicate]

Suppose we have $N$ integer-valued variables $i_1$, $i_2$, $\cdot\cdot\cdot$, $i_N$, such that each variable can take integer values from 0 to $k$, and the sum of these $N$ variables is also equal to ...
0
votes
2answers
31 views

Invertible subblocks

I'm interested in invertible matrices that are built out of invertible sub-blocks. For example, four sub-blocks from $GL_n(F)$ (i.e. the group of $n \times n$ invertible matrices over a field $F$) ...
4
votes
1answer
37 views

number of 1-to-1 linear functions on vectorspaces over finite fields

This is not a homework. I just ask this question myself and thought it would be easy to figure out. But I did not get the solution. Let $\mathbb{F}$ be a finite field with $|\mathbb{F}|=q$. Consider ...
1
vote
1answer
193 views

Setting A Paper on Mathematical Puzzles

I need to set a paper for High School Students on Mathematical Puzzles which make the use of logic, simple combinatorics and algebra. Can people provide new and innovative questions. The questions ...
1
vote
0answers
84 views

Question about the elementary divisors of a special matrix

I have the following question: Is there a closed formula for the elementary divisors of the Matrix $M={(m_{ij})}_{i=1,...,n,\ j=1,...,k}$, where ${m}_{ij}$ is the greates common divisor of $i$ and ...
2
votes
1answer
58 views

Commutants for matrices

Let ${\mathbb K}={\mathbb R}$ or $\mathbb C$. Let $V$ be a vector space over $\mathbb K$ and fix a basis $\cal B$ of $V$. We say that a family of vectors of $V$ is nice (relatively to $\cal B$) if if ...
2
votes
1answer
110 views

Number of zero entries in symmetric (0-1)-matrix with full diagonal

Let $S$ be an $n\times n$ symmetric matrix whose diagonal consists only of $1$s and whose other entries are either $0$ or $1$ . If the determinant and rank of $S$ are known, what can be said about ...
18
votes
1answer
246 views

Count the number of bases in a subset

Consider $\mathbb{R}^n$ as a vector space over $\mathbb{R}$. Consider the subset $\mathrm{S}^n = \{(x_1,\ldots,x_n) \in \mathbb{R}^n | x_i = 0 \; \mathrm{or} \; 1\;\forall i = 1,\ldots,n\}$. How many ...
3
votes
1answer
120 views

“Sorting” matrix entries by swapping rows and columns

Suppose one has an $n \times n$ matrix whose entries are filled with the numbers $1,2,\ldots,n^2$, but not in that order. Q1: What is the largest number of row or column swaps ever needed to end up ...
1
vote
1answer
151 views

Can you determine a formula for this problem?

Given: A list of integers is there.Now there are 2 buckets -bucket A and bucket B.This step is repeated as long as there are numbers left in the list.Integers from start or end of the list are ...
2
votes
1answer
52 views

completely polarized polynomial

Let $A$ be a $(r \times r)$-matrix. From the equation$$ \det\left(1+A\right)=\sum_{0\leq j \leq r} {r \choose j} H_j (A) $$ where $H_j (A)$ are homogenous polynomials of order $j$ in the entries of ...
1
vote
1answer
50 views

Subspaces $\mathcal{C_k}\subset(\mathbb{Z}/2\mathbb{Z})^3$ with $\dim(\mathcal{C_k})=2$

Enumerate all two-dimensional subspaces of the space $(\mathbb Z/2\mathbb{Z})^3$. Obviously we have $|(\mathbb Z/2\mathbb{Z})^3|=2^3=8$ with $$(\mathbb ...
8
votes
1answer
206 views

The first column of the $n$th power for a triangular matrix

I have found a interesting thing but I cannot prove it. Given $k_i$ are positive for any $i\geq1$, and we have $M+1$ by $M+1$ matrix $A$, which is $$ A=\left[\begin{array}{ccccc} 0\\ k_{1} & 0\\ ...
1
vote
3answers
187 views

Ways of selecting at least one man

We have to select a group of 7 out of a group of 9 men and 11 women Q : How many seven member teams consist of at least one man ? Now I know that the answer is ${20 \choose 7}-{11 \choose 7} ...
13
votes
2answers
172 views

Evaluate the determinant $\det\left[ \binom{2n}{n+i-j} \right]_{i,j=0}^{n-1}$

I am trying to show that: \begin{equation} \det\left[ \binom{2n}{n+i-j} \right]_{i,j=0}^{n-1}=\prod_{i=0}^{n-1} \frac{\binom{2n+i}{n}}{\binom{n+i}{n}} \end{equation} I have tried playing with the ...
2
votes
1answer
173 views

Proving determinant product rule combinatorially

One of definitions of the determinant is: $\det ({\mathbf C}) =\sum_{\lambda \in S_n} ({\operatorname {sgn} ({\lambda}) \prod_{k=1}^n C_{k \lambda ({k})}})$ I want to prove from this that ...
3
votes
2answers
70 views

Prove the following $\tan(nA)$ expansion

I've figured out the approach. Writing the expansion of $(1 + x)^n$, then replacing $x$ with $i \tan (A)$. Then separating real and imaginary part and $\tan(nA)$ will be equal to Im/Real. But, after ...
1
vote
1answer
109 views

How many $1$'s could there be in this sequence? Matrix, operator?

For each $(i,j)\in \mathbb{N}^2$, $a(i,j)=1$ or $0$, and 1) $a(i,i)=0$ for all $i$; 2)for fixed $i$, there is at most one $j$ such that $a(i,j)=1$. Suppose we know that there is a finite $\kappa$ such ...
1
vote
2answers
105 views

Analyzing a recurrence relation given by a Toeplitz matrix

Let $p$ be an odd prime, and $M_p$ be the $p\times p$ Toeplitz matrix over $\mathbb{F}_2$ given by $a_0=a_1=1$ and $a_{-p+1}=1$, e.g. for $p=5$ we have $$M_5=\left[\begin{array}{ccccc} 1 & & ...
1
vote
0answers
100 views

Cauchy-Binet formula for squares

Using the convention of the wikipedia article, Cauchy-Binet formula states that --for $A, \, n\times m$ and $B, \, m\times n$ matrices-- $$ \det(AB) = \sum_{S\in\tbinom{[n]}m} ...
0
votes
0answers
46 views

cryptographyVs matrices

I need a good example(s) and justification to the following. If any one can help, I am so glad to them. I understand the original computation. However, I am little confused in writing coding and ...
1
vote
2answers
83 views

Finding $\dim(A_1 + A_2 +\cdots + A_n)$ [duplicate]

Possible Duplicate: The calculation of $\dim(U + V + W)$ Given a linear space $V$ and subspaces $A_i \subseteq V$ such that $1\leq i \leq n.$ To find $\dim(A_1 + A_2 +\cdots + A_n)$ it ...
1
vote
0answers
24 views

order of elements in a partition using Maple

I determined this whole partition but I just want to have the finer the partition for example: I have this ...
5
votes
0answers
147 views

Points and lines covering them

Let $n$ be a positive integer. A subset $S$ of points in plane satisfies the following conditions: a) We can't find $n$ lines in plane, such that every element of $S$ belongs to at least one of these ...
2
votes
1answer
200 views

The number of subspaces of a vector space

Let $V$ be a vector space of dimension $n$ over $\mathbb{F}_q$, and let $U$ be a subspace of dimension $k$. I want to compute the number of subspaces $W$ of $V$ of dimension $m$ such that $W\cap U=0$. ...
3
votes
0answers
129 views

How to invert this function on matrices which involves the permanent?

I'm interested in understanding whether a particular natural function on matrices, closely related to the permanent of a matrix, is invertible, and whether its inverse admits a simple closed form. The ...
2
votes
2answers
131 views

Exercise at the Beginning of Part II in Fulton's Book on Young Tableaux

In Fulton's Book Young Tableaux, there's an Exercise at the beginning of part II for which I cannot find a solution (there doesn't seem to be one for this exercise in my copy of the book). It reads: ...
1
vote
1answer
407 views

Probability of full rank of a random matrix.

Suppose, $G$ is a $k \times n$ binary matrix with $\operatorname{rank}(G) = k$. The first $k$ columns of $G$ are linearly independent and the next $n-k$ columns are linear combinations of the first ...
1
vote
1answer
112 views

number of invertible 0-1 matrices

Define the set $S_n=\{A_n| A_n \hbox{is invertible 0-1 matrix}\}$. What is the size of $S_n$? When $n=2$, it is easy to see $\sharp S_2=6$. I guess $\sharp S_n=\prod_{k=1}^n(2^n-2^{k-1})$.
2
votes
0answers
148 views

Obtaining any linear combination of functions

Suppose $X$, $Y$, and $Z$ are finite sets. If we have a function $$f : X \longrightarrow Y$$ and another $$g : Y \longrightarrow Z$$ then the composite function $g \circ f$ has the property that $$ ...

1 2