Matrislerde maksimum carpimi elde etme

Question

Elimizde pozitif tanimli, girdileri tam sayi olan ve hic bir satir ve sutunu tamamen sifir olmayan $n\times n$'lik bir $A$ matrisi olsun. Bunu hangi $x=(x_1,\cdots,x_n) \in \mathbb R^n$ ile carparsak ($xA=y=(y_1,\cdots,y_n)$) tum $i$'ler icin $y_i \leq 1$ sarti ile $\sum \limits_{i=0}^nx_i$ maksimum olur? (ya da daha yuksek bir deger elde ederiz, maksimuma yaklasiriz?)

Soru genel oldugu icin cevaplanmayabilir, fakat bu cevaba ulasmak icin hangi tarz yontemler kullanabiliriz? Eger matris ornegi verilecekse en az $3\times3$'luk bir matris olmasini rica ederim.

Ek olarak: Bence bu deger  $\frac 12$'den kucuk olmali.

Comments

Mesela A matrisi 3x3 lük bir birim matris olsun. $x=(x_1,x_2,x_3)$ olsun. O zaman $xA=(x_1,x_2,x_3)$ olur. $x_1\leq1$ , $x_2\leq1$ , $x_3\leq1$ . Dolayısıyla $x_1+x_2+x_3\leq3$ oluyor. Başka kısıtlamalar var mı? Neden $\frac{1}{2}$ den küçük olmalı?. Sorunun cevabını ben de merak etmeye başladım.

---

Baska kisitlama yok yanilmiyorsam. (asal) $p$-yogunluk egimi (epey islemden sonra gosterilebilir) bunun icin bir ust sinir, o da maksimum $\frac{1}{2}$ olur.

---

isinize yarar mi bilemedim ama soyle bir seyler karaladim
$\langle x , Ay \rangle = \|y\|_2$
$|\langle x , Ay \rangle | \leq \|x\|_2\|Ay\|_2$

$\|y\|_2 \leq \|x\|_2\|Ay\|_2$

$\frac{\|Ay\|_2}{\|y\|_2} \geq \|x\|_2$

$\|A\| \geq \|x\|_2$ (Bu hamleden cok emin degilim)

$\|x\|_1 \leq \sqrt{n} \|x\|_2 \leq \sqrt{n} \|A\|$

$\sum{x_i}$ leri sinirlayamadim ama $\sum{|x_i|}$ ler icin bir ust sinir buldugumu dusunuyorum

---

Soruyu sorduğum zamanlardaki kafama dönemiyorum şu an ama bence o girdiler de pozitif olmalı.

---

Ece'nin yorum ile bakınca soruyu iyi sormamış olduğumu düşünüyorum. Türkçem çok kötüymüş. Muhtemelen iyi sorduğumu düşünmüş olmalıyım o zamanlar.

Kerem'in dediği tarzda bir soru sorduğumu düşünüyorum. 
https://en.wikipedia.org/wiki/Linear_programming

Answer 1

Sonuçta aradığınız şey $x_i$'lerin bir lineer kombinasyonu. Bu lineer kombinasyonun bir maksimum değeri yoktur. Ama eğer kısıtlar varsa (ve bu kısıtlar lineer denklemler ya da eşitsizlikler ise), doğrusal programlama yöntemleri ile maksimum değer bulunabilir.

Comments

Soruyu duzelttim. Eksik ve hata varmis soruda.

---

Sanırım aradığınızı burada bulabilirsiniz:

https://en.wikipedia.org/wiki/Linear_programming