Construction of all MDS and involutory MDS matrices

• URL: http://arxiv.org/abs/2403.10372v2
• Date: Tue, 13 Aug 2024 14:11:01 GMT
• Title: Construction of all MDS and involutory MDS matrices
• Authors: Yogesh Kumar, P. R. Mishra, Susanta Samanta, Kishan Chand Gupta, Atul Gaur,
• Abstract summary: We propose two algorithms for a hybrid construction of all $ntimes n$ MDS and involutory MDS matrices over a finite field $mathbbF_pm$. The proposed algorithms effectively narrow down the search space to identify $(n-1) times (n-1)$ MDS matrices.
• Score: 7.171901763517741
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In this paper, we propose two algorithms for a hybrid construction of all $n\times n$ MDS and involutory MDS matrices over a finite field $\mathbb{F}_{p^m}$, respectively. The proposed algorithms effectively narrow down the search space to identify $(n-1) \times (n-1)$ MDS matrices, facilitating the generation of all $n \times n$ MDS and involutory MDS matrices over $\mathbb{F}_{p^m}$. To the best of our knowledge, existing literature lacks methods for generating all $n\times n$ MDS and involutory MDS matrices over $\mathbb{F}_{p^m}$. In our approach, we introduce a representative matrix form for generating all $n\times n$ MDS and involutory MDS matrices over $\mathbb{F}_{p^m}$. The determination of these representative MDS matrices involves searching through all $(n-1)\times (n-1)$ MDS matrices over $\mathbb{F}_{p^m}$. Our contributions extend to proving that the count of all $3\times 3$ MDS matrices over $\mathbb{F}_{2^m}$ is precisely $(2^m-1)^5(2^m-2)(2^m-3)(2^{2m}-9\cdot 2^m+21)$. Furthermore, we explicitly provide the count of all $4\times 4$ MDS and involutory MDS matrices over $\mathbb{F}_{2^m}$ for $m=2, 3, 4$.

Related papers

• The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
  We show that this problem has randomized communication complexity $Omega(frac1kcdot n2log|mathbbF|)$. As an application, we obtain an $Omega(frac1kcdot n2log|mathbbF|)$ space lower bound for any streaming algorithm with $k$ passes.
  arXiv  Detail & Related papers  (2024-10-26T06:21:42Z)
• A note on MDS Property of Circulant Matrices [3.069335774032178]
  In $2014$, Gupta and Ray proved that the circulant involutory matrices over the finite field $mathbbF_2m$ can not be maximum distance separable (MDS) This article delves into circulant matrices possessing these characteristics over the finite field $mathbbF_2m$.
  arXiv  Detail & Related papers  (2024-06-22T16:00:00Z)
• On MDS Property of g-Circulant Matrices [3.069335774032178]
  We first discuss $g$-circulant matrices with involutory and MDS properties. We then delve into $g$-circulant semi-involutory and semi-orthogonal matrices with entries from finite fields.
  arXiv  Detail & Related papers  (2024-06-22T15:18:31Z)
• A Characterization of Semi-Involutory MDS Matrices [3.069335774032178]
  In symmetric cryptography, maximum distance separable (MDS) matrices with computationally simple inverses have wide applications. Many block ciphers like AES, SQUARE, SHARK, and hash functions like PHOTON use an MDS matrix in the diffusion layer.
  arXiv  Detail & Related papers  (2024-06-18T17:57:46Z)
• A Systematic Construction Approach for All $4\times 4$ Involutory MDS Matrices [1.3332839594069594]
  We present several characterizations of involutory MDS matrices of even order. We propose a technique to systematically construct all $4 times 4$ involutory MDS matrices over a finite field.
  arXiv  Detail & Related papers  (2024-04-12T05:37:42Z)
• On the Counting of Involutory MDS Matrices [0.0]
  This paper enumerates Hadamard MDS and involutory Hadamard MDS matrices of order $4$ within the field $mathbbF_2r$. It also derives the count of Hadamard-MDS (NMDS) and involutory Hadamard NMDS matrices, each with exactly one zero in each row, of order $4$ over $mathbbF_2r$.
  arXiv  Detail & Related papers  (2023-09-29T18:57:00Z)
• One-sided Matrix Completion from Two Observations Per Row [95.87811229292056]
  We propose a natural algorithm that involves imputing the missing values of the matrix $XTX$. We evaluate our algorithm on one-sided recovery of synthetic data and low-coverage genome sequencing.
  arXiv  Detail & Related papers  (2023-06-06T22:35:16Z)
• Fast $(1+\varepsilon)$-Approximation Algorithms for Binary Matrix Factorization [54.29685789885059]
  We introduce efficient $(1+varepsilon)$-approximation algorithms for the binary matrix factorization (BMF) problem. The goal is to approximate $mathbfA$ as a product of low-rank factors. Our techniques generalize to other common variants of the BMF problem.
  arXiv  Detail & Related papers  (2023-06-02T18:55:27Z)
• Spectral properties of sample covariance matrices arising from random matrices with independent non identically distributed columns [50.053491972003656]
  It was previously shown that the functionals $texttr(AR(z))$, for $R(z) = (frac1nXXT- zI_p)-1$ and $Ain mathcal M_p$ deterministic, have a standard deviation of order $O(|A|_* / sqrt n)$. Here, we show that $|mathbb E[R(z)] - tilde R(z)|_F
  arXiv  Detail & Related papers  (2021-09-06T14:21:43Z)
• Non-PSD Matrix Sketching with Applications to Regression and Optimization [56.730993511802865]
  We present dimensionality reduction methods for non-PSD and square-roots" matrices. We show how these techniques can be used for multiple downstream tasks.
  arXiv  Detail & Related papers  (2021-06-16T04:07:48Z)
• Learning Over-Parametrized Two-Layer ReLU Neural Networks beyond NTK [58.5766737343951]
  We consider the dynamic of descent for learning a two-layer neural network. We show that an over-parametrized two-layer neural network can provably learn with gradient loss at most ground with Tangent samples.
  arXiv  Detail & Related papers  (2020-07-09T07:09:28Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.