IMC 2001, Ημέρα 2, Θέμα 4
Let be an complex matrix such that for each and the determinant of the matrix is zero. Prove that and that there exists a permutation such that the matrix
has all of its nonzero elements above the diagonal.
Πρωτότυπο από το επίσημο PDF

Η μεταγραφή συγκρίθηκε σύμβολο προς σύμβολο με το πρωτότυπο, όχι ακόμα από άνθρωπο.
Δούλεψε τουλάχιστον 45 λεπτά πριν ανοίξεις τη λύση.
Επίσημη λύση
Solution. We will only prove (2), since it implies (1). Consider a directed graph with vertices and a directed edge from to when . We shall prove that it is acyclic.
Assume that there exists a cycle and take one of minimum length . Let be the vertices the cycle goes through and let be a permutation such that for . Observe that for any other we have for some , otherwise we would obtain a different cycle through the same set of vertices and, consequently, a shorter cycle. Finally
Since is acyclic there exists a topological ordering i.e. a permutation such that whenever there is an edge from to . It is easy to see that this permutation solves the problem.
Μεταγραφή από το επίσημο κείμενο λύσεων, σελίδα 4. Η μεταγραφή δεν έχει ελεγχθεί δεύτερη φορά· αν έχεις αμφιβολία, κοίτα το πρωτότυπο.
Θέμα αρχείου: η εκφώνηση είναι το επίσημο κείμενο (μεταγραμμένο, με το πρωτότυπο παραπάνω). Η ταξινόμηση ανά αντικείμενο και η δυσκολία εκτιμήθηκαν αυτόματα· υποδείξεις και λύση στα ελληνικά προστίθενται σταδιακά.
Πώς πήγε;
Οι κινήσεις που σημειώνεις επιστρέφουν νωρίτερα στη διαλογή.