A Linear Algebra Problem(唯一性的判定)

A Linear Algebra Problem

Time Limit: 3000/1000MS (Java/Others)     Memory Limit: 65535/65535KB (Java/Others)

Submit Status

God Kufeng is the God of Math. However, Kufeng is not so skilled with linear algebra, especially when dealing with matrixes.

One day, Captain Chen has a problem with matrix, here is the problem:

Given a n×n matrix A, what is the solution of n×n matrix X for the equation AX+XA=2A?

Captain Chen is a nice Captain, he wants to solve the equation only when A is a diagonal matrix, which means Aij=0 holds for all i≠j .

“That’s easy!” says Kufeng, “the answer is simply X=I, when I is the Identity Matrix.”

“But… is it the only solution for the equation above?” Captain Chen asks.

Kufeng cannot answer this question, can you help him?

Input

The first line of input is a number n, giving the size of matrix A and X. (1≤n≤1000)

Then comes a single line with n numbers, x1,x2,?,xn, where xi is the value of Aii. (−10000≤xi≤10000)

Output

If the answer is unique, output UNIQUE, otherwise output NOT UNIQUE

Sample input and output

Sample Input Sample Output
3
1 2 3
UNIQUE
2
1 -1
NOT UNIQUE

Hint

For the second sample input, A=(100−1), there can be more than one possible solutions for X, for example, X=(1001) and X=(1101) both satisfy the equation, so the answer is not unique.

题目大意:

  给你一个n维的对角矩阵A,然后有一个n维的矩阵X,使得AX+XA=2A的等式成立的条件下,要让X唯一,那么A应该满足什么样的条件?

解题思路:

  刚读完题目后,以为是个找规律的题目,但是一想,还是错了,其实就是简单的矩阵推导了。

  首先,对于单位阵X,那么一定有AX+XA=2A成立。现在来考虑,一般的情况。

  令2A=B,那么,B[i,i] = A[i,i]*X[i,i]+X[i,i]*A[i,i] = 2*A[i,i]*X[i,i] = 2*A[i,i] ->如果要使X唯一,那么A[i,i]!=0.

          B[i,j] = A[i,i]*X[i,j]+X[i,j]*A[j,j] = X[i,j]*(A[i,i]+A[j,j])=0 要使得X唯一,那么(A[i,i]+A[j,j])!=0.

  这样一来,我们就发现了,在A的对角线上的元素不能有0和互为相反数的数了。

代码:

# include<cstdio>
# include<iostream>
# include<algorithm>

using namespace std;

# define MAX 1000+4

int a[MAX];

int main(void)
{
    int n;cin>>n;
    int flag = 0;
    for ( int i = 0;i < n;i++ )
    {
        cin>>a[i];
        if ( a[i]==0 )
        {
            flag = 1;
        }
    }
    if ( !flag )
        {
            sort(a,a+n);
            for ( int i = 0;i < n;i++ )
        {
            if ( a[i]>0||flag == 1 )
                break;
            for ( int j = n-1;j >= i;j-- )
            {
                if ( a[j]+a[i]==0 )
                {
                    flag = 1;
                    break;
                }
                else if ( a[j] < 0 )
                    break;
                else
                    continue;
            }

        }
        }
    if ( flag )
        cout<<"NOT UNIQUE"<<endl;
    else
        cout<<"UNIQUE"<<endl;

    return 0;
}

  

时间: 03-26

A Linear Algebra Problem(唯一性的判定)的相关文章

cdoj793-A Linear Algebra Problem

http://acm.uestc.edu.cn/#/problem/show/793 A Linear Algebra Problem Time Limit: 3000/1000MS (Java/Others)     Memory Limit: 65535/65535KB (Java/Others) Submit Status God Kufeng is the God of Math. However, Kufeng is not so skilled with linear algebra

Here’s just a fraction of what you can do with linear algebra

Here’s just a fraction of what you can do with linear algebra The next time someone wonders what the point of linear algebra is, send them here. I write a blog on math and programming and I see linear algebra applied to computer science all the time.

线性代数导论 | Linear Algebra 课程

搞统计的线性代数和概率论必须精通,最好要能锻炼出直觉,再学机器学习才会事半功倍. 线性代数只推荐Prof. Gilbert Strang的MIT课程,有视频,有教材,有习题,有考试,一套学下来基本就入门了. 不多,一共10次课. 链接:https://ocw.mit.edu/courses/mathematics/18-06-linear-algebra-spring-2010/calendar/ SES # TOPICS KEY DATES 1 The geometry of linear e

《Linear Algebra and Its Applications》- 线性方程组

同微分方程一样,线性代数也可以称得上是一门描述自然的语言,它在众多自然科学.经济学有着广阔的建模背景,这里笔者学识有限暂且不列举了,那么这片文章来简单的讨论一个问题——线性方程组. 首先从我们中学阶段就很熟系的二元一次方程组,我们采用换元(其实就是高斯消元)的方法.但是现在我们需要讨论更加一般的情况,对于线性方程,有如下形式: a1x1+a2x2+…anxn = b. 现在我们给出多个这样的方程构成方程组,我们是否有通用的解法呢? 在<Linear Algebra and Its Applica

Memo - Chapter 6 of Strang&#39;s Linear Algebra and Its Applications

1.实对称矩阵的正定 2.实对称矩阵的半正定 3. Sylvester’s law of inertia : 4.Sylvester’s law of inertia 的推论: 5. SVD 6.瑞利伤: Memo - Chapter 6 of Strang's Linear Algebra and Its Applications

Memo - Chapter 3 of Strang&#39;s Linear Algebra and Its Applications

1.正交向量.正交空间.正交补空间 2.号称是本书最重要的配图 3.向量的cosine距离,投影变换,最小二乘 4.正交基与Schmidt正交化与QR分解 5.函数空间,傅里叶级数,Hilbert空间 Memo - Chapter 3 of Strang's Linear Algebra and Its Applications

《Linear Algebra and Its Applications》-矩阵运算

可以说第一章<Linear Algebra and Its Applications>着重介绍了线性代数中几个核心概念(向量.矩阵和线性方程组)之间的关系(方程的同解性),那么下面这本书开始分别介绍这几个核心概念,比如从这篇文章开始,会简单的介绍矩阵方面的内容. 首先对于我们定义的计算工具(矩阵),我们有必要研究其运算规律,这个方法在定义很多新的运算符号的时候都是适用的.矩阵的加减法这里就不用累述的,非常好理解,这篇文中我们主要来讨论矩阵的乘法运算的定义过程. 其实不管是从离散的角度还是在线性

Machine Learning - III. Linear Algebra Review (Week 1, Optional)

机器学习Machine Learning - Andrew NG courses学习笔记 矩阵和向量及其表示介绍 what are matrices矩阵 matrix is just another way for saying, is a 2D or a two dimensional array. dimension of the matrix is going to be written as the number of row times the number of columns in

Coursera公开课机器学习:Linear Algebra Review(选修)

这节主要是回顾了下线性代数的一些简单知识. 矩阵与向量 矩阵 由$m\times n$个数$a _{ij}(i=1,2,...,m;j=1,2,...,n)$排成的$m$行$n$列的数表,称为$m$行$n$列的矩阵,简称$m\times n$矩阵,记作: $$ \matrix{A}= \begin{bmatrix} a _{11} & a _{12} & \cdots & a _{1n} \cr a _{21} & a _{22} & \cdots & a