Problem O: Linear Algebra Done What

## Problem O: Linear Algebra Done What

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 12  Solved: 4
[Submit][Status][Web Board]

## Description

Every student in SUSTech should learn linear algebra. But what can we do with linear algebra? Let's see.

A $$n*n$$ square matrix $$A$$ can be written as $$A = \left[ \begin{matrix} a_{11} & a_{12} & \cdots & a_{1n}\\ a_{21} & a_{22} & \cdots & a_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ a_{n1} & a_{n2} & \cdots & a_{nn} \end{matrix} \right]$$. The transpose of $$A$$ is $$A^T = \left[ \begin{matrix} a_{11} & a_{21} & \cdots & a_{n1}\\ a_{12} & a_{22} & \cdots & a_{n2} \\ \vdots & \vdots & \ddots & \vdots \\ a_{1n} & a_{2n} & \cdots & a_{nn} \end{matrix} \right]$$.

The matrix $$A$$ is semi positive definite if for any column vector(can be regarded as a $$n*1$$ matrix) $$x \in R^n$$, $$x^T Ax \geq 0$$. Define the F-norm of $$A$$ by $$\|A\|_F^2=\sum_{i=1}^n \sum_{j=1}^n a_{ij}^2$$.

Now we have a $$n*n$$ square matrix $$A$$ which can be decomposed into the form $$A=Q \Lambda Q^T$$, where $$\Lambda = \left[ \begin{matrix} \lambda_1 \\ & \lambda_2 \\ & & \ddots \\ & & & \lambda_n \end{matrix} \right]$$ is a diagonal matrix and $$QQ^T = I = \left[ \begin{matrix} 1 \\ & 1 \\ & & \ddots \\ & & & 1 \end{matrix} \right]$$. We need you to find a $$n*n$$ square semi positive definite matrix $$X$$, such that the value of $$\|A-X\|_F$$ is minimized.

## Input

The first line is the number of the test cases $$T(1\leq T \leq 3)$$.

For each test case, the beginning is an integer $$n(1\leq n \leq 300)$$ denoting the size of the matrix $$A$$.

Then, a $$n*n$$ square real matrix $$Q(-100 \leq q_{ij} \leq 100, 1\leq i,j\leq n)$$.

Last, $$n$$ integers $$\lambda_1, \cdots, \lambda_n(-100 \leq \lambda_i \leq 100, 1\leq i \leq n)$$.

It is guranteed that $$A=Q \Lambda Q^T$$ and $$QQ^T = I$$.

## Output

A $$n*n$$ square semi positive definite real matrix $$X$$. You should keep exactly three decimal place for each real number.

## Sample Input

1
2
1 0
0 1
2 2

## Sample Output

2.000 0.000
0.000 2.000

[Submit][Status]