Deje una matriz real ( ) {\ bf A} con la propiedad de que cualquier colección de k columnas es de rango completo.k ≤ n
P: ¿Hay una manera eficiente de encontrar determinísticamente un vector modo que la matriz aumentada conserve la misma propiedad que : cualquier columna tiene rango completo.
Nota importante: una matriz que tiene esta propiedad es el generador de un código Reed-Solomon : agregar columnas que preserven su estructura Vandermonde conserva la propiedad de rango.
Respuestas:
Si elige uniformemente al azar del hipercubo , la matriz tendrá la propiedad deseada con probabilidad . [ 0 , 1 ] n [ A a ] 1a [0,1]n [A a] 1
fuente