Skip to main content

All Questions

Filter by
Sorted by
Tagged with
14 votes
2 answers
655 views

Number triangle

This question arose just out of curiosity. Note the triangle of 0-1's below, whose construction is as follows. Choose any number, say 53 as done here. The first line of the triangle is the binary ...
DSM's user avatar
  • 1,216
13 votes
1 answer
468 views

Near-linear mappings from $\mathbb F_p$ to $\mathbb R$

$\newcommand{\F}{{\mathbb F}}$ $\newcommand{\R}{{\mathbb R}}$ $\renewcommand{\phi}{\varphi}$ Let $p\ge 5$ be a prime. If the functions $\phi_1,\phi_2,\phi_3\colon\F_p\to\R$ satisfy $\phi_1(x)+\...
Seva's user avatar
  • 23k
11 votes
2 answers
387 views

Bounds for the difference in the number of ones in $M$ and $M^{-1}$

If $M$ is a full rank $n$ by $n$ binary matrix over $\mathbb{F}_2$, how much larger or smaller can the number of $1$s in $M^{-1}$ be, compared to the number of $1$s in $M$? Clearly the identity matrix ...
Simd's user avatar
  • 3,377
10 votes
1 answer
807 views

How many Lie and associative algebras over a finite field are there?

This question is related to the following general question: Given a variety of (non-associative) algebras $\mathcal V$, a finite field $\mathbb{F}_q$, with $q$ elements, and a positive integer $n$, ...
Thiago's user avatar
  • 398
9 votes
1 answer
543 views

On the number of polynomials that divide $x^{q-1}-1$ in some subspaces of $\mathbb F_q[x]$

Let $\mathbb F_q$ be a finite field (where $q$ is in general a power of a prime), and let $e, k$ be positive integers with $k \leq e < q-1$. Let $f_0(x), \ldots, f_k(x) \in \mathbb F_q[x]$ be ...
Sfarla's user avatar
  • 307
9 votes
0 answers
270 views

The number of non-singular $n\times n$ matrices over $\mathbb{F}_2$ with exactly $k$ non-zero entries

Suppose $M_{n}^{k}$ is the number of non-singular $n\times n$ matrices over $\mathbb{F}_2$, that have exactly $k$ non-zero entries. Is there some sort of formula to calculate $M_n^k$? If $k < n$ ...
Chain Markov's user avatar
  • 2,618
8 votes
1 answer
531 views

How large can the dimension of a 'Span of powers of a finite field basis' be?

Let $p$ be a prime. For finite field $\mathbb{F}_{p^k}$ and $d\in\mathbb{Z}^+$, I am considering the following quantity, where we interpret the field $\mathbb{F}_{p^k}$ also as a $\mathbb{F}_p$-vector ...
actcon's user avatar
  • 89
7 votes
2 answers
843 views

Dimension of incomplete matrix over finite fields.

Hi, Suppose one has an incompletely specified $2^n \times 2^n$ matrix over some fixed finite field $\mathbb{F}_{p^k}$. In fact, one knows that the diagonal entries are zero and all other entries are ...
Rob Myers's user avatar
  • 1,291
7 votes
2 answers
589 views

On a matrix problem in the field $\mathbb F_2$

Given $M$ a symmetric matrix in $\mathbb F_2^{n\times n}$ having $\mathsf{det}_\mathbb R(M)\neq0$ (non-singular in reals) and satisfying $PMP'=(M+J+I)$ or $P(M+J+I)P'=M$ where $P$ is a permutation ...
Turbo's user avatar
  • 13.9k
7 votes
1 answer
253 views

Enumerating subspaces of $\mathbb{F}_q^n$ in terms of words and inversions

When $q$ is a prime power, then on the one hand the $q$-binomial coefficient $\binom{n}{k}_q$ equals the number of $k$-dimensional subspaces of $\mathbb{F}_q^n$, and on the other hand it is the ...
Martin Brandenburg's user avatar
7 votes
2 answers
441 views

How to count the number of tensors over a finite field of tensor rank $r$?

For simplicity, work over $\mathbb F_2$ and only consider order-$3$ equilateral tensors. For $r\in\mathbb Z_{>0}$, how many tensors $\mathfrak{T}\in\mathsf{Ten}_{n}^{\otimes 3}(\mathbb F_2)$ are ...
Yihan Zhang's user avatar
7 votes
0 answers
300 views

Arrangement of subspaces over finite fields

I'm trying to find out what is already known about the following setup. Let $V$ be an $n$-dimensional vector space over a finite field $F_q$ (I'm mostly interested in the case where $q$ is prime), and ...
user38495's user avatar
  • 1,062
6 votes
1 answer
458 views

Vector with many non-zero coordinates

Given finite field $\mathbb{F}_q$, positive integers $n$ and $k<n$. Given $k$-dimensional subspace $X$ of $\mathbb{F}_q^n$, for which $m=m(q,k,n)$ may we find for sure a vector in $X$ with at least ...
Fedor Petrov's user avatar
6 votes
1 answer
297 views

Covering the finite plane with lines

This is, essentially, a geometrically rendered version of the question I asked a week ago, with the emphases slightly shifted; it seems more natural and appealing (to me, at least) in this form. Let ...
Seva's user avatar
  • 23k
5 votes
1 answer
394 views

Disjoint union of affine subspaces contains a larger affine subspace

I'd like to say that a large structured subset of the $n$-dimensional Boolean cube $\{0,1\}^n$ contains a non-trivial affine subspace. To be more specific, I want to prove/disprove that for some ...
Alex Golovnev's user avatar
4 votes
1 answer
237 views

Intersection of the general linear group $\text{GL}_n(\mathbb{F}_q)$ and an affine subspace over a finite field

Let $\mathbb{F}_q$ be a finite field of $q$ elements, let $\text{M}_n(\mathbb{F}_q)$ be the vector space of $n \times n$ matrices over $\mathbb{F}_q$, let $\text{GL}_n(\mathbb{F}_q)$ be the group of $...
Kleo's user avatar
  • 43
4 votes
1 answer
317 views

On the real and finite field rank of a $0/1$ matrix - I

Let $M\in\{-1,0,+1\}^{n\times n}$ be a matrix of rank $r$. Consider the matrix $f(M)\in\{0,+1\}^{mn\times mn}$ where $0$ in $M$ is replaced by $m\times m$ all $0$ matrix, $+1$ in $M$ is replaced by $m\...
Turbo's user avatar
  • 13.9k
3 votes
2 answers
303 views

Asymptotics of A000613

The general linear group $GL_n(\mathbb{F}_2)$ acts on the powerset $2^{{\mathbb{F}_2}^n \setminus \{0\}}$ by multiplication: $A \cdot S := \{Ax \in {\mathbb{F}_2}^n : \, x \in S\}$, for an invertible ...
Colin Tan's user avatar
  • 331
3 votes
3 answers
611 views

On MDS code property

Is there a code that is Maximum Distance Separable and not isomorphic to Reed Solomon Codes? When is a MDS code isomorphic to Reed Solomon Code? Is there an easy test? If so, could someone provide ...
Turbo's user avatar
  • 13.9k
3 votes
1 answer
427 views

Ranks of higher incidence matrices of designs

In 1978 Doyen, Hubaut and Vandensavel proved that if $S$ is a Steiner triple system $S(2,3,v)$ then the $GF(2)$ rank of its incidence matrix $N$ is $$ Rk_{2}(N)=v-(d_{p}+1), $$ where $d_{p}$ is the ...
Felix Goldberg's user avatar
3 votes
0 answers
116 views

Trace of Symmetric matrices in fixed rank

I am solving some problem related to symmetric matrices over a finite field $\mathbb{F}_q$ and I am stuck at the following problem: For every $a\in\mathbb{F}_q $, let $S_a(t,m)$ be the set of all $m\...
Singh's user avatar
  • 179
2 votes
1 answer
612 views

Inner product over finite field

sorry for informals but is my first post. In Coding theory (exactly in Coding theory a first course - San ling and Chaoping) found this definition: $\langle , \rangle :\mathbb{F}_q^n\times\mathbb{F}_q^...
Javier Astorga's user avatar
2 votes
0 answers
111 views

Inseparable field extensions of degree p and linear independence

Let $F$ be a field of characteristic $p$; let $\alpha \in F$ such that $\alpha \neq \beta^p$ for any $\beta \in F$, and let $K := F(x)$ where $x=\sqrt[p]{\alpha}$. Is it true that the elements $1,(x-...
adam chapman's user avatar
2 votes
0 answers
113 views

Complexity of tensor decomposition vector over $\Bbb F_q$ or $\Bbb Z$

Suppose we have a matrix $$T\in\Bbb K^{n^k\times m}$$ and a target vector $v\in\Bbb F_q^m$ where $m<n^k$ and $1<k$ holds. We need to find $k$ vectors $u_1,\dots,u_k\in\Bbb K^n$ such that $$v=...
Turbo's user avatar
  • 13.9k
1 vote
1 answer
391 views

System of equations - Proof that a solution exists

Let $ a = (a_1,a_2, \ldots,a_{10})\in \{ 0,1\}^{10}$ be a binary vector of length $10$. Question: Without using a computer-aided method, how to prove that there exists binary vectors $x_{i,j} \in \{ ...
user avatar
1 vote
1 answer
153 views

Schur complement and depermuting an algorithm for $\mathsf{determinant}\bmod2$

Let $$M=\begin{bmatrix}A&B\\C&D\end{bmatrix}$$ be a matrix in $\mathbb F_2^{n\times n}$ where $A\in\mathbb F_2$ and $D\in\mathbb F_2^{(n-1)\times(n-1)}$ are square. Through the determinant ...
Turbo's user avatar
  • 13.9k
1 vote
1 answer
145 views

How many matrices $C \in \mathrm{M}_3(\mathbb{F}_q)$ such that $\det(C-A)=\det(C-B) = 1$?

I am studying the special unit-graph $G$ on $M_3(\mathbb{F}_q).$ Now, I want to estimates the upper bound for the second largest eigenvalue of adjacency matric of $G.$ One of questions that I need is ...
user avatar
1 vote
0 answers
162 views

Number of full-rank binary matrices with given column Hamming weights [closed]

What is the number of $m \times n$ matrices over $\mbox{GF}(2)$ that share the following constraints : They have full rank ($\mbox{rank} = m$, given that $m<n$). Their columns have the given ...
Sapiens's user avatar
  • 111
1 vote
0 answers
150 views

Counting non-zero Gramians of Grassmanians over finite field

In case of $\mathbb{F}_{2}$, we can obtain the number of all reduced row echelon forms (so called Grassmannians) for some m$\times$n full rank matrices by the following gaussian polynomial, $$ \binom{...
mathcat's user avatar
  • 11
1 vote
0 answers
88 views

On the real and finite field rank of a $0/1$ matrix - II

Let $M\in\{-\ell,\dots,-1,0,+1,\dots,+\ell\}^{n\times n}$ be a matrix of rank $r$ where $\ell\geq1$ such that there is a permutation matrix in $\{0,1\}^{m\times m}$ of order $2\ell$. Fix a permutation ...
Turbo's user avatar
  • 13.9k
1 vote
0 answers
75 views

Symmetric matrices of hyperbolic and elliptic type with certain kind of trace zero

I have been working on a problem related to determinantal varieties in symmetric matrices. I am stuck at the following point and would like to get some reference/help for the following question. Let $\...
Singh's user avatar
  • 179
1 vote
0 answers
413 views

Combinatorial Interpretation of an Extension of Gaussian Polynomials

It is well-known that the Gaussian polynomial (or Gaussian coefficient, q-binomial coefficient) $\binom{n}{k}_q$ counts the number of $k$-dimensional subspaces of an $n$-dimensional vector space over $...
Ken Gonzales's user avatar
0 votes
1 answer
146 views

Does the Plotkin bound mean that one can not achieve the Singleton bound asymptotically?

I am a little confused with the relationship between various bounds for error correcting codes. Does the Plotkin bound mean that one can not achieve the Singleton bound asymptotically? That is, is ...
liu_c_6's user avatar
  • 11
0 votes
1 answer
390 views

An upper bound for skew symmetric rank 2 matrices

Earlier, I had asked a similar question but that was not the correct problem where I got stuck. After a few quick answer, I realized that and I apologize for that. Let $B_m$ be the space of all skew-...
Singh's user avatar
  • 179
0 votes
0 answers
99 views

Invertible matrices with bounded nonnegative coefficients

I am teaching a class in linear algebra and I asked myself the following question: what is the chance to get an invertible matrix if I write a random one? My impulsive answer is "very likely"...
Andrea Marino's user avatar
0 votes
0 answers
54 views

Rank decomposition of matrices over $\mathbb F_2$

Given an integer matrix $M\in\mathbb Z^{n\times n}$ of real rank $k$ what is the minimum and maximum number of rank $1$ matrices $B_1$ to $B_t$ we require so that $M\equiv\sum_{i=1}^tB_i\bmod 2$? If $...
Turbo's user avatar
  • 13.9k
0 votes
0 answers
299 views

Question on rank of matrices over $\mathbb F_2$

$A$ is a square matrix in $\mathbb F_2^{n\times n}$ of rank $k\leq n-1$. $B$ is a square matrix in $\mathbb F_2^{n\times n}$ of rank $n$. $T$ is a square matrix in $\mathbb F_2^{n\times n}$ of rank $1$...
Turbo's user avatar
  • 13.9k