I have to following problem $$\max_{x}x^TAx+b^Tx\quad \mathrm{s.t.}\quad  x^Tx\leq c,$$ where $A$ is real, symmetric and positive semi-definite.  Firstly I tried to solve the problem with the KKT, but that didn't lead to any good results for arbitrary matrices.  So now I argue in the following way  Since $x^TAx \leq \lambda_{max}x^Tx$, I get $x^TAx+b^Tx\leq \lambda_{max}x^Tx + b^Tx$ and with the constraint $x^Tx\leq c$ this leads to $$x^TAx+b^Tx\leq \lambda_{max}x^Tx + b^Tx \leq \lambda_{max}c+b^Tx$$ So my solution would be $$x=\sqrt{c}v_{max},$$ where $v_{max}$ is the unit-eigenvector corresponding to the largest eigenvalue $\lambda_{max}$ of $A$. The thing that confuses me about this solution is that the solution does not depend on $b$ at all, so I am sure it is not correct...
123910
Consider the $n$-dimensional quadratically constrained quadratic optimization problem  $$\begin{array}{ll} \text{maximize} &amp; \frac12 x^T A x + b^T x\\ \text{subject to} &amp; \| x \|_2 \le 1\end{array}$$  where $A$ is a symmetric $n\times n$ matrix that may be indefinite. Given the symmetry of the constraint, is there a nice closed-form solution, perhaps in terms of the eigendecomposition of $A$?
72001
For the Quadratic Form $X^TAX; X\in\mathbb{R}^n, A\in\mathbb{R}^{n \times n}$ (which simplifies to $\Sigma_{i=0}^n\Sigma_{j=0}^nA_{ij}x_ix_j$), I tried to take the derivative wrt. X ($\Delta_X X^TAX$) and ended up with the following:  The $k^{th}$ element of the derivative represented as  $\Delta_{X_k}X^TAX=[\Sigma_{i=1}^n(A_{ik}x_k+A_{ki})x_i] + A_{kk}x_k(1-x_k)$  Does this result look right? Is there an alternative form?  I'm trying to get to the $\mu_0$ of Gaussian Discriminant Analysis by maximizing the log likelihood and I need to take the derivative of a Quadratic form. Either the result I mentioned above is wrong (shouldn't be because I went over my arithmetic several times) or the form I arrived at above is not the terribly useful to my problem (because I'm unable to proceed).  I can give more details about the problem or the steps I put down to arrive at the above result, but I didn't want to clutter to start off. Please let me know if more details are necessary.  Any link to related material is also much appreciated.
53609
Let $f(x) = \frac{1}{2}x^tQx-b^tx, Q\in\mathbb{R}^{n\times n}$   symmetric definite positive and $b\in\mathbb{R}^n$. Let $x^0, x^1,  \cdots, x^n\in\mathbb{R}^n$ and define $\delta^j = x^j-x^0$, $\gamma^j  = \nabla f(x^j)-\nabla f(x^0)$, $j=0,1\cdots,n$. Prove that the vectors $\{\delta^j\}_{j=1}^n$ are linearly independent, then   $$\overline{x} = x^n-[\delta^1\cdots \delta^n]\cdot[\gamma^1\cdots  \gamma^n]^{-1}\cdot\nabla f(x^n)$$ is a global minimizer of $f$   So, that's what I did:  $$\nabla f(x) = Qx-b^t\implies \gamma^j = Qx^j-b^t-(Qx^0-b^t) = Q(x^j-x^0)\implies\\\gamma^j = Q\delta^j\implies\delta^j = Q^{-1}\gamma^j$$  So  $$\overline{x} = x^n-[Q^{-1}\gamma^1\cdots Q^{-1}\gamma^n]\cdot[\gamma^1\cdots  \gamma^n]^{-1}\cdot\nabla f(x^n) =\\ x^n -Q^{-1}[\gamma^1\cdots \gamma^n][\gamma^1\cdots \gamma^n]^{-1}\cdot\nabla f(x^n) = x^n-Q^{-1}\nabla f(x^n) \implies \\\overline{x} = x^n-Q^{-1}(Qx^n-b^t) = x^n-x^n+Q^{-1}b^t = Q^{-1}b^t$$  So I need to prove $\overline{x} = Q^{-1}b^t$ is a global minimizer? Also, I need to use linear independence of $\{\delta^j\}$ to something. I guess it is related with the inverse matrix. Maybe linear independence of $\{\delta\}^j$ implies that that matrix has an inverse, but I don't know why.  Also, as I recall, $f(x)$ is quadratic and therefore convex. So shouldn't it has only one minimum? (therefore, since it is convex, it's the global?) So I should need to prove only that $\overline{x}$ is a local minimum? In that case I should only have to calculate $\nabla f(\overline{x}) = Q(Q^{-1}b^t)-b^t = 0$. The second derivative is just $Q$ and is definite positive. So: first derivative zero, second derivatie def. positive. Therefore this point $\overline{x}$ should be a minimum.  Even though I think I solved the exercise I don't know what all this means. It could just have asked if $Q^{-1}b^t$ is a global minimum. I think it is trying to show me a process of finding a global minimum for a quadratic function but I don't see the motivation.
8771
If $A=CBC$, where $A$,$B$,$C$ are symmetric matrices and $A$,$B$ are given find $C$.  $A$,$B$,$C$ are assumed to be real valued and $B$ is positive definite matrix. Does the unique solution always exist ? What additional assumptions are needed to obtain unique solution.
47529
I'm trying to find a closed form solution of the following quadratic form for $x$.  $x^{T}Dx = c$  where $c$ is just a constant placeholder for some terms on the other side.  I know that, because $D$ is positive semi-definite, this equation describes a level curve of an ellipsoid in $x$, which gives me hope that there exists a closed form solution of the form $x = \frac{a\pm  \sqrt{z}}{b}$, for some $a, z, b$ (which may be matrices or vectors).   Do you know if this solution exists and if so how it is determined?
17546
Let $A \in \mathbb{R}^{p \times p}$ and $B \in \mathbb{R}^{q \times q}$ be nonsymmetric positive definite matrices in the sense that $v^T A v &gt; 0, \forall v \in \mathbb{R}^p$ and $v^T B v &gt; 0, \forall v \in \mathbb{R}^q$.  I know that $A \oplus B$, i.e. a matrix with a block structure \begin{align} \pmatrix{A &amp; 0 \\          0 &amp; B} \end{align} is positive definite and I also know that if $p=q$, then $A+B$ is positive definite as well.  Can I say that as well if the blocks overlap partially? When?   For instance a matrix as follows: \begin{align} \pmatrix{a_{11} &amp; a_{12} &amp; a_{13} &amp; a_{14} &amp; 0&amp; 0\\          a_{21} &amp; a_{22} &amp; a_{23} &amp; a_{24}&amp; 0&amp; 0\\          a_{31} &amp; a_{32} &amp; a_{33} + b_{11} &amp; a_{34} + b_{12} &amp;b_{13}&amp;b_{14}\\          a_{41} &amp; a_{42} &amp; a_{43} + b_{21} &amp; a_{44} + b_{22} &amp;b_{23}&amp;b_{24}\\          0 &amp; 0 &amp; b_{31} &amp; b_{32} &amp;b_{33}&amp;b_{34} \\          0 &amp; 0 &amp; b_{41} &amp; b_{42} &amp;b_{43}&amp;b_{44}} \end{align}
90090
Can we have the following?     For matrices $A$ and $B$, if $A \succeq B \implies \overline\sigma(A) \ge \overline\sigma(B)$?    where $\overline\sigma(\cdot)$ means the largest singular value.
25793
Given that $A$ is a symmetric matrix, find $X$ that solves $$\mathop {\min }\limits_X {\left\| {A - X{X^T}} \right\|_F}$$  I think that the problem can be solved using eigenvalue or singular value decomposition technics. $XX^T=A$ seems an obvious solution, but the problem is that $XX^T$ is positive semidefinite, while $A$ may not be, although they are both symmetric.  At this point I am thinking about taking eigenvalue decomposition of A, then replace the negative eigenvalues in the middle diagonal matrix with 0-s (denote the resulting matrix by $\bar{A}$). But am having difficulties to understand why  $XX^T=\bar{A}$ gives the $X$ with minimal distance from A.
52434
Prove, for real $X$, that $\text{rank}(X^TX)=\text{rank}(X)$.  Could anyone please help me with this problem? I've tried to use full-rank factorization and rank-related theorems mentioned in my book but still failed to solve this. I am learning linear algebra by myself and my book has no solutions manual so I find it really hard to get used to solve linear algebra problems.    Many thanks in advance for your help!
111738
It is easy to find the minimum of $\|Ax-b\|_2$, when $A$ has full column rank. But how is the case when we add the constraint $\|x\|_2=1$? Or, to be explicit,  $$\min_{\|x\|_2=1}\|Ax-b\|_2=?$$  My idea is to construct the corresponding Lagrange function  $$L(x,\lambda) = (Ax-b)^T(Ax-b) + \lambda(x^T x - 1)$$  Differentiate the function with respect to $x,\lambda$, we have  $$A^T A x - A^T b + \lambda x = 0$$  $$x^T x=1$$  However, I find it hard to move forward to get the answer. Could anyone help me? Thanks a lot!
25981
Let $A \in \mathbb{R}^{n\times n}$ be a positive definite matrix, $x \in \mathbb{R}^n$ and $c \in \mathbb{R} \setminus \{0\}$. I got to determine the maximum  $$\max\{c^Ty:y\in \mathcal{E} (A,x)\}$$  where $\mathcal{E} (A,x)$ is an ellipsoid defined by $A$ and $x$.   How can I determine this maximum? Can anyone give me a hint?
69134
Given is a linear regression problem, where we have one training point, which is 1-dimensional: $x \in R_{&gt;0}$ and the corresponding output, $y \in R$. We duplicate the feature, such that we have one training point with two (identical) features.   For this, we have to determine if we can apply the closed form solution $\beta = (X^TX)^-1*X^T*y$. Then we have to solve the linear regression problem by taking into account that $f(X) = ||y-X*\beta||^2$ is convex.   Application of the closed form solution: For this I want to determine if $X^TX$ has full rank. Given is $X = (1,x_{11},x_{12})$. Hence $X^T*X$ results in:  \begin{bmatrix}     1 &amp; x_{11} &amp; x_{12}  \\     x_{11} &amp; x_{11}^2 &amp; x_{11}x_{12}  \\     x_{12}  &amp; x_{11}x_{12} &amp; x_{12}^2   \end{bmatrix}   This matrix seems to have full rank (independent column vectors), so the closed form solution is applicable. Correct? Is there another way to determine the rank without explicitly calculating $X*X^T$?   For minimizing $f(\beta)$ I would derive $||y-X*\beta||^2$ and set it equal to zero.
120572
Suppose we have $n\times n$ matrix $A$ having only positive elements and satisfying the property $a_{ij}=1/a_{ji}$ (a matrix satisfying this property is called a reciprocal matrix).  If its largest eigenvalue $λ_{max}$ is equal to $n$, then the matrix $A$ satisfies the property (consistency property) $a_{ij}a_{jk}=a_{ik}$ where $i,j,k=1,2,...,n$.    I already found an example of $5\times 5$ reciprocal matrix  to show this condition:  \begin{bmatrix}1&amp;1/2&amp;1&amp;1&amp;1/4\\2&amp;1&amp;2&amp;2&amp;1/2\\1&amp;1/2&amp;1&amp;1&amp;1/4\\1&amp;1/2&amp;1&amp;1&amp;1/4\\4&amp;2&amp;4&amp;4&amp;1\end{bmatrix}  It has simple characteristic equation $λ^5-5λ^4=0$, so the eigenvalues of matrix $A$ are $λ=0$ and $λ=5$ and it's shown that $λ_{max}=n=5$.  Is there anyone can help me to give another positive reciprocal matrix example  that has simple characteristic equation and integer number as its eigenvalues ($4\times 4, 5\times 5$ or $6\times 6$ matrix)?
64751
Let $C \in \mathbb{R}^{d \times d}$ be symmetric, and   $$Q = \begin{bmatrix}       \vert &amp; \vert &amp;    &amp; \vert \\       q_1   &amp; q_2   &amp; \dots &amp; q_K  \\       \vert &amp; \vert &amp;    &amp; \vert       \end{bmatrix} \in \mathbb{R}^{d\times K}$$  where $d \geq K$. Using Lagrange multipliers,   $$\begin{array}{ll} \text{maximize} &amp; \mbox{tr} \left( Q^T C Q \right)\\ \text{subject to} &amp; Q^T Q = I\end{array}$$    I am unfamiliar with these kind of constraints with this method, and after reading  I believe the same specific and simple result given is also applicable, and therefore the lagrangian would be:  $$\mathcal{L}(Q,\lambda)=\mathrm{tr}(Q^TCQ)-\left&lt;\lambda,Q^TQ-I\right&gt;$$  where $\lambda\in\mathbb{R}^{K\times K}$, and $\left&lt;\cdot,\cdot\right&gt;$ is the element wise inner product (what kind of makes sense to me since we're actually adding as many constraints as there are elements in these matrices.  In attempting to do that I start taking $\frac{\partial \mathcal{L}}{\partial Q}=O\in\mathbb{R}^{d\times K}$, and compute that LHS element by element; for the $(l,m)$ one:  \begin{equation} 0=\frac{\partial \mathcal{L}}{\partial Q_{lm}}=(CQ+C^TQ)_{lm}-\underbrace{\frac{\partial}{\partial Q_{lm}}\sum_{i,j}\lambda_{i,j}(Q^TQ-I)_{ij}}_{=\lambda_{lm}\frac{\partial (Q^TQ)_{lm}}{\partial Q_{lm}}}=2(CQ)_{lm}-\lambda_{lm}\frac{\partial (q_l^Tq_m)}{\partial q_m(l)} \tag{1}\end{equation}  where in the last step I've used the definition I made at the beginning for $Q$, and $q_m(l)$ denotes the $l$-th component of the column vector $q_m$.  In trying to compute the very last term:  $$\frac{\partial (q_l^Tq_m)}{\partial q_m(l)}=\frac{\partial \left[q_l(1)q_m(1)+ \ldots + q_l(d)q_m(d)\right]}{\partial q_m(l)}= \begin{cases}     q_l(l)\equiv Q_{ll}    &amp; \text{if } l\neq m\\     2q_l(l)\equiv 2Q_{ll}  &amp; \text{if} l=m \end{cases}$$  The whole equality (1) then can be written:  $$0=2(CQ)_{lm}-\lambda_{lm}Q_{ll}(1+\delta_{lm})$$  where $\delta_{lm}$ is the Kronecker delta.  The equation for the other stationary point of the lagrangian, $\frac{\partial \mathcal{L}}{\partial \lambda}=O\in\mathbb{R}^{K\times K}$, for the $(l,m)$ element as well:  $$ 0=\frac{\partial \mathcal L}{\partial \lambda_{lm}}= \frac{\partial }{\partial \lambda_{lm}}\sum_{i,j}\lambda_{i,j}(Q^TQ-I)_{ij}=(Q^TQ-I)_{lm}\tag{2}$$  what obviously leads to $(Q^TQ)_{lm}=\delta_{lm}$.  All this should tell that the columns of $Q$ are eventually the $K$ first eigenvectors of $C$, but I don't know how to continue from here to prove that, supposing I didn't make a mistake. Please I would sincerely appreciate any help.    Edit:  I have rewritten the inner product as a trace of a product of matrices (after seeing ):  $$\left&lt;\lambda,Q^TQ-I\right&gt;=\sum_{i,j}\lambda_{i,j}(Q^TQ-I)_{ij}=\mathrm{tr}(\lambda^TQ^TQ) $$  and have thus managed to do the derivative without losing the matrix format (using formulas from the ):  \begin{align} O=&amp;\frac{\partial \mathcal{L}}{\partial Q}=\frac{\partial}{\partial Q}\mathrm{tr}(Q^TCQ)-\frac{\partial}{\partial Q}\underbrace{\mathrm{tr}(\lambda^T(Q^TQ-I))}_{\mathrm{tr}(\lambda^TQ^TQ)-\mathrm{tr}(\lambda^T)}\\=&amp;(CQ+C^TQ)-(Q(\lambda^T)^T+Q\lambda^T)=2CQ+Q(\lambda+\lambda^T) \end{align}  And this leads to:  $$CQ=Q\underbrace{\left(-\frac{\lambda+\lambda^T}{2}\right)}_{:=\widetilde{\lambda}};\quad CQ=Q$$  If the defined matrix $\widetilde{\lambda}=Q^TCQ$ were diagonal we would already have the result.
46445
I see on Wikipedia that the product of two commuting symmetric positive definite matrices is also positive definite. Does the same result hold for the product of two positive semidefinite matrices?  My proof of the positive definite case falls apart for the semidefinite case because of the possibility of division by zero...
10504
A symmetric matrix $A$ is positive definite if $x^TAx&gt;0$ for all $x\not=0$.  However, such matrices can also be characterized by the positivity of the principal minors.  A statement and proof can, for example, be found on wikipedia:   However, the proof, as in most books I have seen, is very long and involved. This makes sense in a book where you wanted to prove the other theorems anyway. But there has to be a much better way to prove it.     What is the "proof from the book" that positive definite matrices are characterized by their $n$ positive principal minors?
25941
Let $A,B\in M_{n}(\mathbb{R})$ be symmetric, with $A&gt;0$ and $B&gt;0$.  I need to prove that $\det (A+B)&gt;\max (\det(A), \det(B))$.  I want to use Sylvester theorem of having a matrix $D$ so that $D=\operatorname{diag}(1,1,\ldots, 1,-1,-1, \ldots-1,0,0,\ldots,0)$.  Do I need to use it? How do I use it here?  Thank you.