Πόσοι πίνακες;

#1

Πόσοι $n \times n$ αντιστρέψιμοι πίνακες

υπάρχουν ώστε τα στοιχεία τόσο του

όσο και του $A^{-1}$ να ανήκουν στο σύνολο $\{0,1\}$ ;

dement · #2

Έστω

κατάλληλος πίνακας. Αν $A_{km} = 1$ τότε $(A^{-1})_{mk'} = 0$ για κάθε $k' \neq k$ (αλλιώς δε μπορεί το $I_{kk'}$ να ισούται με

).

'Αρα, κάθε στήλη

του πίνακα

πρέπει να περιέχει τουλάχιστον ένα

(αλλιώς ο $I_{nn}$ δε μπορεί να είναι

) και το πολύ ένα

(αλλιώς η αντίστοιχη γραμμή

του $A^{-1}$ μηδενίζεται ολόκληρη). Ομοίως για τις γραμμές του

.

Κατά συνέπεια, ο

πρέπει να είναι της μορφής $A_{km} = \delta_{m, p(k)}$ , όπου

μετάθεση του $\{1, 2, ..., n \}$ .

Αντίστροφα, εύκολα διαπιστώνουμε ότι κάθε τέτοιος πίνακας είναι αντιστρέψιμος με $A^{-1} = A^T$ . Οπότε υπάρχουν

τέτοιοι πίνακες.

#3

Σωστά. Ήταν από διαγωνισμό του Τορόντο του 2005.