חידה יפה באלגוריתמים

[nautilus7791]

חידה יפה באלגוריתמים

נתונה מטריצה ריבועית A n*n שמכילה אפסים ואחדים.נאמר שמטריצה A היא "מוזרה" אם קיים k שלם וחיובי כך ש A בחזקת k שווה לאפס,כלומר קיימת חזקה של מטריצה A שהיא מטריצה עם כל האפסים.בהינתן מטריצה A n*n יש לגלות בזמן O(n^2 האים היא מטריצה מוזרה

 

[Fingertip]

תשובה פשוטה

ראשית, מכיוון שמעל המרוכבים לכל פולינום יש שורש, הרי של-A יש לפחות ערך עצמי מרוכב אחד λ. כעת, אם v הוא ו"ע השייך ל-λ ו-A נילפוטנטית (כלומר, "מוזרה"), אזי:

0 = A^kv = λ^kv​

ולכן λ = 0. מכאן שהערך העצמי היחיד של A הוא 0. בכיוון השני זה קצת יותר מורכב בשביל הודעה בודדת, אבל מצורת ז'ורדן מקבלים שאם הע"ע היחיד הוא 0, אזי המטריצה נילפוטנטית (האפסים של המטריצה "מתפשטים" החל מהאלכסון לכל המטריצה בצורת ז'ורדן עם כל חזקה). לכן כל מה שצריך לעשות הוא לבדוק האם הפולינום האופייני של המטריצה הוא פשוט x^n. חישוב דטרמיננטה אפשר לעשות בסיבוכיות ריבועית (אני חושב... אין לי כח לבדוק, האמת

) וגמרנו. אהד.

 

[nautilus7791]

הפתרון שלך לא עומד בתנאי O(n^2

וגם לא נכון

 

[Fingertip]

לא נכון?

איפה הטעות בהוכחת התנאי ההכרחי והמספיק? אהד.

 

[nautilus7791]

לא עומד בדרישת סיבוכיות זמן ריצה

 

[Fingertip]

כן, את זה הבנתי

רק אמרת שחוץ מזה שהוא לא עומד בסיבוכיות, הוא גם לא נכון, ולא הבנתי למה. הפתרון הנכון באמת חביב. אהד.

 

[amni]

נדמה לי שחישוב פולינום אופייני הוא ריבועי

זה סוג של חישוב דטרמיננטה.

 

[Fingertip]

שוב, אני לא יודע, ואין לי כח לבדוק.

אהד.

 

[amni]

תיקון טעות שלי (כנראה)

חישוב דטרמיננטה בשיטות רגילות הוא בזמן קובי (חזקת 3) ולא ריבועי. יש אמנם שיטות מסובכות מאוד (תיאורטיות) לעשות זאת בפחות זמן , אבל הן לא לעניין מבחינת השאלה. יתכן שבגלל התכונות המיוחדות של המטריצה אפשר לקצר את הזמן לבדיקת נילפוטנטיות של מטריצה לזמן ריבועי. מכיוון שאין לי ספר אלגברה מתקדם תחת ידי (ואין לי זמן) אני לא יכול לבדוק זאת. אשר , להצעה להמיר בעיית נילפוטנטיות של מטריצה בבעיית גרף ללא מעגלים. זה לא מוכר לי, אבל יתכן שזה נכון (דורש הוכחה ).

 

[amni]

נחמד

 

[amni]

וכנראה באותו מחיר זמן מחושב ערך k

 

[nautilus7791]

להלן הפתרון הנכון

מטריצה כזאת מתאימה לגרף מכוון.A בחזקת k שווה לאפס אם ורק אם בגרף לא יהיו מעגלים ו k זה האורך של המסלול הכי ארוך

 

[amni]

תשובתך מראה למה חשוב ללמוד מתמטיקה במדמ"ח

הפתרון שלו גם נכון וגם אלגנטי.

 

[p i o n e e r]

איך אתה בונה את הגרף על סמך המטריצה?

 

[yaeerk]

הזכרת לי נישכחות... ../images/Emo51.gif