Matrixstijfheid

Matrixstijfheid, of matrixrigidity, is een maatstaf uit de lineaire algebra en theoretische informatica die aangeeft hoe ver een gegeven matrix verwijderd is van lage-rang matrices. Voor een n×n-matrix M over een veld F en een gewenste rang r (met 0 ≤ r ≤ n) is de r-stijfheid van M de minimale hoeveelheid ingangen die men moet wijzigen om een matrix te verkrijgen met rank at most r. Concreet spreekt men van R(M, r) als het minimum aantal ingangen dat aangepast moet worden zodat de resultatenmatrix N een rang heeft ≤ r. Een alternatieve formulering geeft aan dat M s-stijf is ten opzichte van r als R(M, r) ≥ s.

Toepassing en belang: Matrixstijfheid werd geïntroduceerd door Leslie Valiant in 1977 als conceptuele route naar lower bounds voor de grootte van circuits die lineaire transformaties berekenen. Als er een familie van expliciete matrices bestaat met hoge stijfheid voor geschikte waarden van r en s, dan volgt daaruit dat bepaalde berekeningen niet met polynomiale circuits kunnen worden uitgevoerd. Het onderwerp verbindt aspecten van combinatoriek en complexiteitstheorie en heeft geleid tot significante theoretische inspanningen naar expliciete constructies met hoge stijfheid.

Voorbeelden en uitdagingen: Een eenvoudig voorbeeld is de identiteitsmatrix I_n. Om de rank terug te brengen tot at most r moet men minstens n − r diagonaalelementen veranderen, zodat het resultaat een diagonaalmatrix met rank r heeft. In het algemeen zijn willekeurige matrices doorgaans vrij stijf, maar expliciete constructies die voor een breed scala aan r gegarandeerd hoge stijfheid bieden blijven een open onderzoeksgebied.