Putnam 2011/A4

#1

Για ποιους φυσικούς

υπάρχει ακέραιος πίνακας ώστε το εσωτερικό γινόμενο κάθε σειράς του πίνακα με τον εαυτό της να είναι άρτιος, ενώ το εσωτερικό γινόμενο κάθε δύο διαφορετικών σειρών να είναι περιττός;

dement · #2

Υπάρχει κατάλληλος πίνακας αν και μόνο αν ο

είναι περιττός.

Για κάθε $n \in \mathbb{Z}_+$ ορίζουμε τον πίνακα $n \times n$ S_n

με $(S_n)_{ij} \equiv 1 - \delta_{ij}$ . Εύκολα διαπιστώνουμε ότι, αν ο

είναι περιττός, ο S_n

είναι κατάλληλος πίνακας.

Αντίστροφα, έστω

κατάλληλος πίνακας για

άρτιο. Προσθέτοντας όλες τις στήλες του στην πρώτη διαπιστώνουμε ότι ο $\det(A)$ είναι άρτιος (αφού κάθε γραμμή του έχει άρτιο αριθμό περιττών στοιχείων). Επειδή κάθε στοιχείο του AA^T

είναι ισότιμο $\mod 2$ με το αντίστοιχο του S_n

συμπεραίνουμε ότι και ο $\det(S_n)$ είναι άρτιος. Όμως, προσθέτοντας ( $\mod 2$ ) όλες τις στήλες του S_n

στην πρώτη και στη συνέχεια αφαιρώντας την πρώτη στήλη από όλες τις άλλες καταλήγουμε σε πίνακα τριγωνικό κάτω με όλα τα στοιχεία της διαγωνίου

. Άρα ο $\det(S_n)$ είναι περιττός και έχουμε άτοπο.

#3

Ωραία Δημήτρη!

Διαφορετικά αν γράψουμε J_n

για τον $n \times n$ πίνακα που έχει παντού άσσους, τότε είναι $\mathrm{rank}(J_n)=1$ και άρα ο J_n

έχει ιδιοτιμή

με πολλαπλότητα n-1

. Επειδή $\mathrm{tr}(J_n) = n$ η άλλη ιδιοτιμή του J_n

ισούται με

.

Άρα ο AA^T = J_n - I_n

έχει ιδιοτιμές $-1,-1,\ldots,-1,n-1$ και άρα $\det(AA^T) = (-1)^{n-1}(n-1) \equiv 1 \bmod 2$ .

$\rule{500pt}{1pt}$

Στην λύση που είδα δείχνει ότι $(J_n-I_n)^2 = \cdots = (n-2)J_n + I_n \equiv I_n \bmod 2$

#4

Ας δούμε ακόμη μια απόδειξη:

Έστω $x_1,\ldots,x_n$ οι γραμμές του πίνακα τις οποίες θεωρούμε ως διανύσματα πάνω από το $\mathbb{F}_2$ . Έστω επίσης $x = (1,1,\ldots,1)$ .

Στην περίπτωση όπου ο

είναι άρτιος, θα δείξω ότι τα $x,x_1,\ldots,x_n$ είναι γραμμικώς ανεξάρτητα. Αυτό ασφαλώς είναι άτοπο αφού αυτά είναι n+1

διανύσματα στο $\mathbb{F}_2^n$ .

Οι συνθήκες δίνει $x_i \cdot x_j = 1 - \delta_{ij}$ . Επίσης $x \cdot x_i = x_i \cdot x_i = 0$ .

Ας υποθέσουμε λοιπόν ότι $\lambda x + \lambda_1 x_1 + \cdots + \lambda_nx_n = 0$ . (*)

Παίρνοντας εσωτερικό γινόμενο στην (*) με το x_1

λαμβάνουμε $\lambda_2 + \cdots + \lambda_n = 0$ ή ισοδύναμα $\lambda_1 + \cdots + \lambda_n = \lambda_1$ .

Ομοίως λαμβάνουμε $\displaystyle{ \lambda_1 + \cdots + \lambda_n = \lambda_1 = \cdots = \lambda_n}$

Αν λοιπόν $\lambda_1 = \cdots = \lambda_n = k$ , τότε $k = \lambda_1 + \cdots + \lambda_n = nk = 0$ αφού ο

είναι άρτιος. Άρα $\lambda_1 = \cdots = \lambda_n = 0$ και από την (*) παίρνουμε και $\lambda = 0$ .

Οπότε όντως τα διανύσματα είναι γραμμικώς ανεξάρτητα και το ζητούμενο αποδείχθηκε.

#5

Demetres έγραψε:Ας δούμε ακόμη μια απόδειξη:

Έστω $x_1,\ldots,x_n$ οι γραμμές του πίνακα τις οποίες θεωρούμε ως διανύσματα πάνω από το $\mathbb{F}_2$ . Έστω επίσης $x = (1,1,\ldots,1)$ .

Στην περίπτωση όπου ο είναι άρτιος, θα δείξω ότι τα $x,x_1,\ldots,x_n$ είναι γραμμικώς ανεξάρτητα. Αυτό ασφαλώς είναι άτοπο αφού αυτά είναι διανύσματα στο $\mathbb{F}_2^n$ .

Οι συνθήκες δίνει $x_i \cdot x_j = 1 - \delta_{ij}$ . Επίσης $x \cdot x_i = x_i \cdot x_i = 0$ .

Ας υποθέσουμε λοιπόν ότι $\lambda x + \lambda_1 x_1 + \cdots + \lambda_nx_n = 0$ . (*)

Παίρνοντας εσωτερικό γινόμενο στην (*) με το λαμβάνουμε $\lambda_2 + \cdots + \lambda_n = 0$ ή ισοδύναμα $\lambda_1 + \cdots + \lambda_n = \lambda_1$ .

Ομοίως λαμβάνουμε $\displaystyle{ \lambda_1 + \cdots + \lambda_n = \lambda_1 = \cdots = \lambda_n}$

Αν λοιπόν $\lambda_1 = \cdots = \lambda_n = k$ , τότε $k = \lambda_1 + \cdots + \lambda_n = nk = 0$ αφού ο είναι άρτιος. Άρα $\lambda_1 = \cdots = \lambda_n = 0$ και από την (*) παίρνουμε και $\lambda = 0$ .

Οπότε όντως τα διανύσματα είναι γραμμικώς ανεξάρτητα και το ζητούμενο αποδείχθηκε.

Πεπερασμένα σώματα, άπειρες εφαρμογές!

Putnam 2011/A4

Putnam 2011/A4

Re: Putnam 2011/A4

Re: Putnam 2011/A4

Re: Putnam 2011/A4

Re: Putnam 2011/A4

Μέλη σε σύνδεση