Given $n\times n$ matrices $A_{1},\ldots,A_{m}$ over a finite field, how can one construct a matrix $\sum_{j}^{m}a_{j}A_{j}$ with the maximal possible rank ?
Dear Farid !
Many thanks for your answer.
Relating your example, on the other hand, if you take
A_{1}=1 & 0 \\ 0 & 0
and
A_{2}=0 & 0 \\0 & 1
then, adding the matrices over F_{2} results in rank=2 matrix.
To sharpen the question over F_{2}:
Do we have to pass over all 2^{m}-1 non-trivial possible combinations
$\sum_{j=1}^{m}a_{j}A_{j}$ and each time record the combination that has a maximal rank or, is there any efficient way to get a maximal rank matrix as above ?
All The Best !
Following example of Peretz, Let i=1,..,n, if we denote E_i i the matrix with 1 on the position (i,i) and 0 everywhere, then the sum of these matrices gives the identity matrix, rank n. If we are on a field F_q, we can follow the same example by taking any non zero entry, we obtain a diagonal matrix with rank n. By this way you can even find the number of combinations which can give a matrix of rank n by combining this result with diagonalization of matrices over finite fields. Unfortunately II have more on diagonalization on real and complex number fields but not much more on finite fields.
Dear Munir !
Thank you for your answer. The question is algorithmic: you are given a set (m matrices) of nXn matrices and you need to create a linear combination out of the given matrices such that the resulting matrix has the greatest rank that can be achieved in this way. The question is how to do it efficiently.
All The Best !
- Badges
- Science topic
- Similar topics
- Mathematics
- Algebra
- Matrix