Wie uniform Proben von singulären Matrizen

Ich möchte einheitlich von allen Singular n von n Bernoulli Matrizen Probe (das ist jeder Eintrag ist 1 oder 0 mit der Wahrscheinlichkeit 1/2). Ich könnte natürlich nur von allen n by n Bernoulli-Matrizen Proben nehmen und diejenigen ablehnen, die nicht singulär sind, aber für jedes moderate n, das extrem ineffizient ist.Wie uniform Proben von singulären Matrizen

Als Beispiel, von den 10000 zufälligen 100 von 100 Matrizen, die ich getestet habe, waren keine singular.

Gibt es eine effiziente Möglichkeit, dies zu tun?

Hier ist ein Test Python-Code, um das Problem zu zeigen.

import numpy as np 
iters = 10000 
n = 100 
count = 0 
for i in xrange(iters): 
    A = np.random.randint(2, size = (n,n)) 
    if (np.linalg.matrix_rank(A) < n): 
     count += 1 
print count

Posted https://mathoverflow.net/questions/155185/how-to-sample-uniformly-from-singular-matrices auf Jan 20.

https://mathoverflow.net/questions/155185/how-to-sample-uniformly-from-singular-matrices hat jetzt einen Algorithmus vorgeschlagen, dieses Problem zu lösen. Die verbleibende Herausforderung besteht darin, herauszufinden, wie es umgesetzt werden kann.

Quelle

2014-01-17 marshall

Eine Idee, die Sie ausprobieren können, besteht darin, die ersten n-1 Zeilen zu generieren und dann die letzte Zeile als lineare Kombination des vorherigen n-1 zu generieren. Dies garantiert eine einzigartige Matrix, aber ich bin mir nicht sicher, wie Sie die Uniformität erreichen würden. –

Ja, ich habe gerade realisiert. Wie auch immer, vielleicht eine nützliche Referenz für zukünftige Generationen http://arxiv.org/pdf/1112.0753.pdf :) –

Diese Frage scheint off-topic zu sein, denn auf dem Spektrum der Fragen reicht von der Programmierung über die Informatik bis zur Forschungsebene Mathematik , diese Frage steht auf dem mathematischen Ende des Spektrums. – mbeckish

Die Kommentare trieben ein wenig weg, so dass ich dieses Posting als Antwort:

Es ist ein Papier hier: http://www.researchgate.net/publication/2729950_Efficient_Generation_of_Random_Nonsingular_Matrices/file/e0b4951d5a6fcc7e67.pdf, die beschreibt, wie nicht-singulär erzeugen und als Erweiterung, singuläre Matrizen über endliche Felder. Da die reellen Zahlen in der Programmierung teilweise begrenzt sind, denke ich, dass sie hier anwendbar sein sollten.

Quelle

2014-01-17 17:41:50

Eine Abhängigkeit von GF (2) wird nicht unbedingt eine Abhängigkeit von Q sein. (Ordentliches Papier jedoch.) – tmyklebu

+1. Ich denke, wenn das OP einen Algorithmus aus einem bestimmten Papier vorgeschlagen hätte und um Hilfe bei der Implementierung gebeten hätte, wäre das eine gute Frage. Fordern Sie die Community auf, das Internet nach Papieren zu durchsuchen, nicht so sehr. – mbeckish

Ich habe die Arbeit nicht gelesen und verstanden, aber auf Seite 7 habe ich Pseudocode für die Erzeugung von Singularmatrizen gesehen. Ist das in der Arbeit unklar? –

Wie uniform Proben von singulären Matrizen

Antwort

Verwandte Themen