Hadamard's maximal determinant problem
জ্যাক হ্যাডামার্ডের নামে নামকরণ করা হ্যাডামার্ডের সর্বাধিক নির্ধারক সমস্যা, 1 বা-1 এর সমান উপাদান সহ একটি ম্যাট্রিক্সের বৃহত্তম নির্ধারক জিজ্ঞাসা করে। 0 বা 1 এর সমান উপাদান সহ ম্যাট্রিক্সের জন্য অনুরূপ প্রশ্নটি সমতুল্য, কারণ নীচে যেমন দেখানো হবে, n আকারের একটি {1,-1} ম্যাট্রিক্সের সর্বাধিক নির্ধারক হল n-1 আকারের একটি {0,1} ম্যাট্রিক্সের সর্বাধিক নির্ধারকের 2n-1 গুণ। 1893 সালের গবেষণাপত্রে হ্যাডামার্ড এই সমস্যাটি উত্থাপন করেছিলেন যেখানে তিনি তাঁর বিখ্যাত নির্ধারক বাউন্ড উপস্থাপন করেছিলেন এবং সাধারণ আকারের ম্যাট্রিক্সের জন্য অমীমাংসিত রয়ে গেছেন। হ্যাডামার্ডের বাউন্ড বোঝায় যে n আকারের {1, −1}-ম্যাট্রিসের সর্বাধিক nn/2 নির্ধারক রয়েছে। হ্যাডামার্ড পর্যবেক্ষণ করেছেন যে সিলভেস্টারের একটি নির্মাণ ম্যাট্রিক্সের উদাহরণ তৈরি করে যা n 2 এর ঘাত হলে সীমা অর্জন করে এবং তার নিজস্ব 12 এবং 20 আকারের উদাহরণ তৈরি করে। তিনি আরও দেখিয়েছেন যে সীমাটি কেবল তখনই অর্জনযোগ্য যখন n সমান 1,2, বা 4 এর গুণিতক। অতিরিক্ত উদাহরণগুলি পরে স্কার্পিস এবং পেলি এবং পরবর্তীকালে অন্যান্য অনেক লেখক দ্বারা নির্মিত হয়েছিল। এই ধরনের ম্যাট্রিক্স এখন হাদামার্ড ম্যাট্রিক্স নামে পরিচিত। তারা নিবিড় অধ্যয়ন পেয়েছে। ম্যাট্রিক্স মাপ n যার জন্য n ষ্ণ 1,2, বা 3 (মোড 4) কম মনোযোগ পেয়েছে। প্রথম দিকের ফলাফল বারবার কারণে, যিনি এন বিজোড়ের জন্য হ্যাডামার্ডের সীমা শক্ত করেছিলেন এবং উইলিয়ামসন, যিনি এন = 3,5,6 এবং 7 এর জন্য সবচেয়ে বড় নির্ধারক খুঁজে পেয়েছিলেন। কিছু গুরুত্বপূর্ণ ফলাফলের মধ্যে রয়েছে বারবা, এহলিচ এবং ওয়াজটাসের কারণে, n ষ্ণ 1,2, বা 3 (মোড 4)-এর জন্য, যা সর্বদা অর্জনযোগ্য নয় বলে জানা যায়, n ষ্ণ 1 বা 2 (মোড 4)-এর জন্য সীমা অর্জনকারী ম্যাট্রিক্সের কয়েকটি অসীম ক্রম, নির্দিষ্ট n ষ্ণ 1 বা 2 (মোড 4)-এর জন্য সীমা অর্জনকারী ম্যাট্রিক্সের সংখ্যা, নির্দিষ্ট n ষ্ণ 1 বা 3 (মোড 4)-এর জন্য সীমা অর্জন না করা ম্যাট্রিক্সের সংখ্যা, তবে এগুলি সম্পূর্ণ গণনার মাধ্যমে সর্বাধিক নির্ধারক হিসাবে প্রমাণিত হয়েছে। পরিসংখ্যানে পরীক্ষার নকশায় {1, −1} ম্যাট্রিক্স এক্স (অগত্যা বর্গ নয়) ব্যবহার করা হয় যার জন্য তথ্য ম্যাট্রিক্স এক্সটিএক্স-এর সর্বাধিক নির্ধারক রয়েছে। (XT স্বরলিপিটি X-এর ট্রান্সপোজকে বোঝায়।) এই ধরনের ম্যাট্রিক্সগুলি ডি-অপ্টিমাল ডিজাইন হিসাবে পরিচিত। যদি এক্স একটি বর্গ ম্যাট্রিক্স হয়, তবে এটি একটি স্যাচুরেটেড ডি-অপ্টিমাল ডিজাইন হিসাবে পরিচিত। হ্যাডামার্ড ম্যাট্রিক্স একটি n × n হ্যাডামার্ড ম্যাট্রিক্সের যে কোনও দুটি সারি অর্থোগোনাল। একটি {1, −1} ম্যাট্রিক্সের জন্য, এর অর্থ হল যে কোনও দুটি সারি এন্ট্রির ঠিক অর্ধেকের মধ্যে পৃথক হয়, যা n একটি বিজোড় সংখ্যা হলে অসম্ভব। যখন n ষ্ণ2 (মড 4) হয়, তখন দুটি সারি যা উভয়ই তৃতীয় সারির অর্থোগোনাল, তারা একে অপরের অর্থোগোনাল হতে পারে না। এই বিবৃতিগুলি একসাথে বোঝায় যে একটি n × n হাদামার্ড ম্যাট্রিক্স কেবল তখনই বিদ্যমান থাকতে পারে যদি n = 1,2, বা 4 এর গুণিতক হয়। হ্যাডামার্ড ম্যাট্রিক্সগুলি ভালভাবে অধ্যয়ন করা হয়েছে, তবে এটি জানা যায় না যে প্রতিটি n এর জন্য একটি n × n হ্যাডামার্ড ম্যাট্রিক্স বিদ্যমান কিনা যা 4 এর ধনাত্মক গুণিতক। সবচেয়ে ছোট n যার জন্য একটি n × n হাদামার্ড ম্যাট্রিক্স বিদ্যমান বলে জানা যায় না তা হল 668। {1, −1} ম্যাট্রিক্সের সমতা এবং স্বাভাবিকীকরণ নিম্নলিখিত যে কোনও ক্রিয়াকলাপ, যখন একটি {1, −1} ম্যাট্রিক্স আর-এ সঞ্চালিত হয়, তখন কেবল একটি বিয়োগ চিহ্ন দ্বারা আর-এর নির্ধারক পরিবর্তন করেঃ একটি সারির নেতিবাচকতা। একটি কলামের নেতিবাচকতা। দুটি সারির বিনিময়। দুটি কলামের বিনিময়। দুটি {1, −1} ম্যাট্রিক্স, R1 এবং R2, সমতুল্য হিসাবে বিবেচিত হয় যদি R1 কে উপরের ক্রিয়াকলাপগুলির কিছু ক্রম দ্বারা R2-এ রূপান্তরিত করা যায়। সমতুল্য ম্যাট্রিক্সের নির্ধারকগুলি সমান, সম্ভবত একটি চিহ্ন পরিবর্তন ব্যতীত, এবং প্রায়শই সারি এবং কলামগুলির নেতিবাচকতা এবং বিন্যাসের মাধ্যমে R কে প্রমিত করা সুবিধাজনক। একটি {1, −1} ম্যাট্রিক্সকে স্বাভাবিক করা হয় যদি এর প্রথম সারি এবং কলামের সমস্ত উপাদান 1-এর সমান হয়। যখন একটি ম্যাট্রিক্সের আকার বিজোড় হয়, তখন কখনও কখনও একটি ভিন্ন স্বাভাবিকীকরণ ব্যবহার করা দরকারী যেখানে প্রতিটি সারি এবং কলামে জোড় সংখ্যক উপাদান 1 এবং বিজোড় সংখ্যক উপাদান −1 থাকে। প্রথম দুটি অপারেশন ব্যবহার করে এই স্বাভাবিককরণগুলির মধ্যে যে কোনও একটি সম্পন্ন করা যেতে পারে। {1, −1} এবং {0,1} ম্যাট্রিক্সের জন্য সর্বাধিক নির্ধারক সমস্যার সংযোগ স্বাভাবিক n × n {1, −1} ম্যাট্রিক্সের সেট থেকে (n − 1) × (n-1) {0,1} ম্যাট্রিক্সের সেট পর্যন্ত এক-থেকে-এক মানচিত্র রয়েছে যার অধীনে নির্ধারকের মাত্রা 21 − n গুণক দ্বারা হ্রাস করা হয়। এই মানচিত্রটি নিম্নলিখিত ধাপগুলি নিয়ে গঠিত। {1, −1} ম্যাট্রিক্সের সারি 1 কে সারি 2 থেকে n পর্যন্ত বিয়োগ করুন। (এটি নির্ধারককে পরিবর্তন করে না।) 2 থেকে n পর্যন্ত সারি এবং 2 থেকে n পর্যন্ত কলাম নিয়ে গঠিত (n−1) × (n−1) সাবম্যাট্রিক্সটি বের করুন। এই ম্যাট্রিক্সে 0 এবং −2 উপাদান রয়েছে। (এই সাবম্যাট্রিক্সের নির্ধারক মূল ম্যাট্রিক্সের মতোই, যা ধাপ 1-এ প্রাপ্ত ম্যাট্রিক্সের কলাম 1-এ একটি কোফ্যাক্টর সম্প্রসারণ সম্পাদন করে দেখা যায়।) একটি {0,1} ম্যাট্রিক্স পেতে সাবম্যাট্রিক্সকে −2 দ্বারা ভাগ করুন। (এটি নির্ধারককে (−2) 1 − n দ্বারা গুণ করে।) উদাহরণস্বরূপঃ এই উদাহরণে, মূল ম্যাট্রিক্সের নির্ধারক −16 রয়েছে এবং এর চিত্রের নির্ধারক 2 = −16· (−2) −3 রয়েছে। যেহেতু একটি {0,1} ম্যাট্রিক্সের নির্ধারক একটি পূর্ণসংখ্যা, তাই একটি n × n {1, −1} ম্যাট্রিক্সের নির্ধারক হল 2n − 1 এর একটি পূর্ণসংখ্যা গুণিতক। সর্বাধিক নির্ধারক গ্রাম ম্যাট্রিক্সের উপরের সীমা ধরা যাক R একটি n/n {1, −1} ম্যাট্রিক্স। আর-এর গ্রাম ম্যাট্রিক্সকে ম্যাট্রিক্স জি = আরআরটি হিসাবে সংজ্ঞায়িত করা হয়। এই সংজ্ঞা থেকে জানা যায় যে, G একটি পূর্ণসংখ্যা ম্যাট্রিক্স, যা প্রতিসম, ধনাত্মক-সমপরিমিত, যার ধ্রুবক তির্যক যার মান n-এর সমান। R-এর সারিগুলিকে অগ্রাহ্য করলে বা সেগুলিতে একটি বিন্যাস প্রয়োগ করলে G-এর সারি এবং সংশ্লিষ্ট কলামে একই নেতিবাচকতা এবং বিন্যাস প্রয়োগ করা হয়। আমরা ম্যাট্রিক্স G′ = RTR-ও সংজ্ঞায়িত করতে পারি। ম্যাট্রিক্স জি হল ভেক্টরের একটি সেটের সাধারণ গ্রাম ম্যাট্রিক্স, যা আর-এর সারির সেট থেকে উদ্ভূত হয়, যেখানে জি 'হল আর-এর কলামের সেট থেকে উদ্ভূত গ্রাম ম্যাট্রিক্স। প্রতিটি পরিচিত সর্বাধিক-নির্ধারক ম্যাট্রিক্স একটি স্বাভাবিক ম্যাট্রিক্সের সমতুল্য, তবে এটি সর্বদা হয় কিনা তা জানা যায় না। হ্যাডামার্ডের বাউন্ড (সমস্ত n-এর জন্য) হ্যাডামার্ডের বাউন্ড এই বলে উদ্ভূত করা যেতে পারে যে |det R। = (ডেট G) 1/2 ≤ (ডেট nI) 1/2 = nn/2, যা এই পর্যবেক্ষণের ফল যে nI, যেখানে I হল n বাই n আইডেন্টিটি ম্যাট্রিক্স, ম্যাট্রিক্সের মধ্যে 1-4 সন্তোষজনক বৈশিষ্ট্যগুলির মধ্যে সর্বাধিক নির্ধারকের অনন্য ম্যাট্রিক্স। ডেট আর অবশ্যই 2n−1-এর একটি পূর্ণসংখ্যার গুণিতক হতে হবে যা আরেকটি প্রদর্শন প্রদান করতে ব্যবহার করা যেতে পারে যে হ্যাডামার্ডের সীমা সবসময় অর্জনযোগ্য নয়। যখন n বিজোড় হয়, তখন আবদ্ধ nn/2 হয় অ-পূর্ণসংখ্যা বা বিজোড় হয় এবং তাই যখন n = 1 ব্যতীত তা অর্জনযোগ্য নয়। যখন n = 2k এবং k বিজোড়, তখন 2-এর সর্বোচ্চ ঘাত 2k, যা 2n−1-এর চেয়ে কম, যদি না n = 2 হয়। অতএব, হ্যাডামার্ডের সীমা অপ্রাপ্য যদি না n = 1,2, অথবা 4-এর গুণিতক হয়। যখন n বিজোড় হয়, তখন গ্রাম ম্যাট্রিক্সের জন্য বৈশিষ্ট্য 1 কে G-তে শক্তিশালী করা যেতে পারে যা একটি বিজোড়-পূর্ণসংখ্যা ম্যাট্রিক্স। এটি একটি তীক্ষ্ণ উপরের সীমা প্রাপ্ত করার অনুমতি দেয়ঃ |det R। = (ডেট G) 1/2 ≤ (ডেট (n-1) I + J) 1/2 = (2n−1) 1/2 (n−1) (n−1)/2, যেখানে J হল সর্ব-এক ম্যাট্রিক্স। এখানে (n-1) I + J হল সর্বাধিক-নির্ধারক ম্যাট্রিক্স যা পরিবর্তিত বৈশিষ্ট্য 1 এবং বৈশিষ্ট্য 2-4-কে সন্তুষ্ট করে। এটি যে কোনও সারির সেট এবং সংশ্লিষ্ট কলামের সেটকে-1 দ্বারা গুণ করা পর্যন্ত অনন্য। 2n−1 একটি নিখুঁত বর্গক্ষেত্র না হলে এই সীমা অর্জনযোগ্য নয় এবং তাই যখন n ষ্ণ 3 (মড 4) হয় তখন তা কখনই অর্জনযোগ্য নয়। ইলিচ-ওয়াজটাস n ষ্ণ 2 (মোড 4) এর জন্য আবদ্ধ যখন n জোড় হয়, তখন R এর সারির সেটকে দুটি উপসেটে ভাগ করা যেতে পারে। জোড় ধরনের সারিতে জোড় সংখ্যা 1 এবং জোড় সংখ্যা-1 থাকে। বিজোড় ধরনের সারিতে বিজোড় সংখ্যক উপাদান 1 এবং বিজোড় সংখ্যক উপাদান-1 থাকে। একই ধরনের দুটি সারির বিন্দু গুণফল n (মড 4)-এর সমতুল্য; বিপরীত ধরনের দুটি সারির বিন্দু গুণফল n + 2 (মোড 4)-এর সমতুল্য। যখন n ষ্ণ2 (মড 4), এটি বোঝায় যে, R-এর সারিগুলিকে ক্রমবিন্যাস করে, আমরা আদর্শ রূপটি ধরে নিতে পারি, যেখানে A এবং D প্রতিসম পূর্ণসংখ্যা ম্যাট্রিক্স যার উপাদানগুলি 2 (মোড 4)-এর সমতুল্য এবং B একটি ম্যাট্রিক্স যার উপাদানগুলি 0 (মোড 4)-এর সমতুল্য। 1964 সালে, এলিচ এবং ওজটাস স্বাধীনভাবে দেখিয়েছিলেন যে এই ফর্মের সর্বাধিক নির্ধারক ম্যাট্রিক্সে, A এবং D উভয়ই আকার n/2 এবং (n−2) I + 2J এর সমান এবং B হল শূন্য ম্যাট্রিক্স। এই সর্বোত্তম রূপটি যে কোনও সারির সেট এবং সংশ্লিষ্ট কলামের সেটকে-1 দ্বারা গুণ করা এবং সারি ও কলামে একযোগে একটি বিন্যাস প্রয়োগ করা পর্যন্ত অনন্য। এটি আবদ্ধ ডেট R ≤ (2n−2) (n−2) (n−2)/2 বোঝায়। এলিচ দেখিয়েছেন যে, যদি R সীমা অর্জন করে এবং R-এর সারি ও কলামগুলি এমনভাবে বিন্যস্ত করা হয় যাতে G = RRT এবং G′ = RTR উভয়েরই আদর্শ রূপ থাকে এবং উপযুক্তভাবে স্বাভাবিক করা হয়, তাহলে আমরা লিখতে পারি যেখানে W, X, Y, এবং Z হল (n/2) × (n/2) ম্যাট্রিক্স যেখানে ধ্রুবক সারি এবং কলামের যোগফল w, x, y, এবং z যা z = −w, y = x, এবং w2 + x2 = 2n−2-কে সন্তুষ্ট করে। অতএব 2n−2 দুটি বর্গের যোগফল হিসাবে প্রকাশযোগ্য না হলে এলিচ-ওয়াজটাস সীমানা অর্জনযোগ্য নয়। যখন n বিজোড় হয়, তখন সারিগুলিকে −1 দ্বারা গুণ করার স্বাধীনতা ব্যবহার করে, এই শর্ত আরোপ করা যেতে পারে যে R-এর প্রতিটি সারিতে জোড় সংখ্যা 1 এবং বিজোড় সংখ্যা −1 থাকে। এটি দেখানো যেতে পারে যে, যদি এই স্বাভাবিকীকরণটি ধরে নেওয়া হয়, তবে জি-এর বৈশিষ্ট্য 1 কে জি-তে শক্তিশালী করা যেতে পারে যা এন (মোড 4)-এর সমতুল্য পূর্ণসংখ্যা উপাদান সহ একটি ম্যাট্রিক্স। যখন n ষ্ণ 1 (মোড 4), বারবার সর্বোত্তম রূপটি এই শক্তিশালী বৈশিষ্ট্যটিকে সন্তুষ্ট করে, কিন্তু যখন n ষ্ণ 3 (মোড 4), তখন তা হয় না। এর অর্থ হল পরবর্তী ক্ষেত্রে বন্ধনকে তীক্ষ্ণ করা যেতে পারে। এলিচ দেখিয়েছেন যে যখন n ষ্ণ 3 (মড 4), তখন শক্তিশালী বৈশিষ্ট্য 1 বোঝায় যে G-এর সর্বাধিক-নির্ধারক রূপটিকে B − J হিসাবে লেখা যেতে পারে যেখানে J হল সর্ব-এক ম্যাট্রিক্স এবং B একটি ব্লক-তির্যক ম্যাট্রিক্স যার তির্যক ব্লকগুলি (n-3) I + 4J আকারে হয়। উপরন্তু, তিনি দেখিয়েছেন যে সর্বোত্তম আকারে, ব্লকের সংখ্যা, s, নীচের সারণিতে দেখানো n-এর উপর নির্ভর করে এবং প্রতিটি ব্লকের হয় আকার r বা আকার r + 1 রয়েছে যেখানে n = 11 ব্যতীত যেখানে দুটি সম্ভাবনা রয়েছে, সর্বোত্তম রূপটি যে কোনও সারির সেট এবং সংশ্লিষ্ট কলামের সেটকে −1 দ্বারা গুণ করা এবং সারি ও কলামে একযোগে একটি বিন্যাস প্রয়োগ করা পর্যন্ত অনন্য। এই সর্বোত্তম রূপটি সেই সীমানার দিকে নিয়ে যায় যেখানে v = n − rs হল r + 1 আকারের ব্লকের সংখ্যা এবং u = s − v হল r আকারের ব্লকের সংখ্যা। কোহন সীমাটি বিশ্লেষণ করে নির্ধারণ করেন যে, n = 3 ছাড়াও, এটি শুধুমাত্র n = 112t2 ± 28t + 7 ধনাত্মক পূর্ণসংখ্যা t-এর জন্য একটি পূর্ণসংখ্যা। তমুরা দ্বিঘাত রূপের যৌক্তিক সমতুল্যতার উপর হাস-মিনকোভস্কি উপপাদ্য ব্যবহার করে সীমার প্রাপ্যতার উপর অতিরিক্ত বিধিনিষেধ তৈরি করেছিলেন এবং দেখিয়েছিলেন যে ক্ষুদ্রতম n> 3 যার জন্য এলিচের সীমাটি ধারণযোগ্যভাবে অর্জনযোগ্য 511। আকার 21 পর্যন্ত সর্বাধিক নির্ধারক n = 21 আকার পর্যন্ত {1, −1} ম্যাট্রিক্সের সর্বাধিক নির্ধারকগুলি নিম্নলিখিত সারণিতে দেওয়া হয়েছে। সাইজ 22 হল সবচেয়ে ছোট ওপেন কেস। সারণিতে, D (n) 2n−1 দ্বারা ভাগ করা সর্বাধিক নির্ধারককে উপস্থাপন করে। সমতুল্যভাবে, ডি (এন) এন-1 আকারের একটি {0,1} ম্যাট্রিক্সের সর্বাধিক নির্ধারককে উপস্থাপন করে। তথ্যসূত্র সমন্বিত নকশা ম্যাট্রিক্স গণিতে অমীমাংসিত সমস্যা