Construction of all MDS and involutory MDS matrices

In this paper, we propose two algorithms for a hybrid construction of all n× n MDS and involutory MDS matrices over a finite field Fpᵐ, respectively. The proposed algorithms effectively narrow down the search space to identify (n-1) × (n-1) MDS matrices, facilitating the generation of all n × n MDS and involutory MDS matrices over Fpᵐ. To the best of our knowledge, existing literature lacks methods for generating all n× n MDS and involutory MDS matrices over Fpᵐ. In our approach, we introduce a representative matrix form for generating all n× n MDS and involutory MDS matrices over Fpᵐ. The determination of these representative MDS matrices involves searching through all (n-1)× (n-1) MDS matrices over Fpᵐ. Our contributions extend to proving that the count of all 3× 3 MDS matrices over F2ᵐ is precisely (2ᵐ-1)⁵(2ᵐ-2)(2ᵐ-3)(2²ᵐ-9· 2ᵐ+21). Furthermore, we explicitly provide the count of all 4× 4 MDS and involutory MDS matrices over F2ᵐ for $m=2, 3, 4$.