2
votes
1answer
24 views

complexity of solving $n \times n$ rank deficient linear system

I think it is known that given a nonsingular $A \in \mathbb{R}^{n \times n}$ and $b \in \mathbb{R}^n$, solving a linear system $Ax =b$ for $x$ can be done in $O(n^3)$ steps. Now assume $A$ is of rank ...
11
votes
3answers
290 views

Eigenvalue test faster than $O\left(n^3\right)$?

Given a real $n\times n$ matrix $A$, one can find the eigenvalues in $O\left(n^3\right)$ by using say, the $QR$ algorithm. Now, what if we guess an eigenvalue $\lambda_0$, and we want to know if it's ...
11
votes
3answers
161 views

Is there an easy way to find the sign of the determinant of an orthogonal matrix?

I just learned that if a matrix is orthogonal, its determinant can only be valued 1 or -1. Now, if I were presented with a large matrix where it would take a lot of effort to calculate its ...
1
vote
1answer
134 views

Tree Traversal - Simple Puzzle type Issue.

This is a puzzle like question,based on Fibonacci like structure of the tree. Actually it is a short question with out any complex concepts. It appears bit big,since I have added explanations with ...
0
votes
0answers
26 views

Algorithmic Complexity of Linear Independence

Given n m-dimensional vectors. You can determine linear independence by Gaussian elimination. http://en.wikipedia.org/wiki/Gaussian_elimination#Computational_efficiency Checking linear independence ...
1
vote
0answers
49 views

number of multiplication steps required to solve Ax = b

If we can factorize $A$ in $LU$, We can solve $Ax = b$ in 2 steps: Solve $Lc = b$ for c Solve $Ux = c$ for x As per the Linear algebra book by Gilbert Strang, each step takes $n^2/2$ number of ...
0
votes
0answers
29 views

Matrix scaling problem for Unitary matrices

I would like to know about the complexity of the following problem. Given a ($n\times n$) unitary matrix U and two row-vectors R and C of rational numbers, all of which less than 1, with ...
1
vote
0answers
131 views

How to compute this recursion in linear time?

Can the following iterative update on a $n$-element vector $\mathbf{x}_t$ be computed in $O(n)$ computations? \begin{align*} \mathbf{x}_{t+1} & = a_t\mathbf{y}_t + \mathbf{A}_t \mathbf{x}_t \,,\\ ...
0
votes
1answer
16 views

Stability and complexity of some functions

Can someone check if my solutions/arguments on this exercise are correct? Thanks! Are the following statements true or false? $\sin (x)=\mathcal{O}(1)$ as $x \rightarrow \infty$ $\sin ...
2
votes
0answers
60 views

Asymptotic behavior of $L^2$ norm for increased matrix dimensions

I am playing with matrices which are linear combinations of identity matrix, Pauli spin matrices, $\sigma_x$ and $\sigma_z$ or their tensor products. For example, let the matrix be $H$. So, $H$ could ...
0
votes
0answers
34 views

Polytime programming

Given a linear system of the form: $$x_r = a$$ $$x_j = b$$ $$c_1x_1 + c_2x_2 ... c_nx_n = n$$ $$x_1 + x_2 + x_3 ... x_n = k $$ $$0 \leq a,b,x_1, x_2, x_3 ... x_n \leq 1$$ $$k \geq 0$$ How quickly ...
7
votes
1answer
117 views

complexity of matrix multiplication

For $n\times n$ dimensional matrices, it is known that calculating $\operatorname{tr}\{AB\}$ needs $n^2$ scalar multiplications. How many scalar multiplications are needed to calculate ...
6
votes
3answers
268 views

Which is easier to work out: determinant or inverse?

Suppose $A\in M_n(R)$ be a $n\times n$ matrix over some ring $R$. Which of the following two tasks is easier? to work out $\det(A)$; to work out $A^{-1}$. More specifically, I want to know the ...
0
votes
2answers
75 views

How to work out the inverse matrix $A^{-1}$ ?

Suppose A is a matrix over some ring R (might be non-commutative). How to work out the inverse matrix $A^{-1}$?
6
votes
2answers
1k views

Minimum distance of a binary linear code

I need to find parameters $n$, $k$ and $d$ of a binary linear code from its Generator Matrix. How can I find parameter $d$ efficiently? I know the method that compute all the codewords and take ...
5
votes
1answer
180 views

Complexity of a quadratic program

I have a quadratic program: $$\displaystyle\min_{\mathbf{X}} (\mathbf{X^TQX +C^TX}) \quad{} \text{subject to} \quad{} \mathbf{A X \leq Y}$$ $\mathbf{Q}$ is positive definite and is $N \times N$, ...
4
votes
1answer
136 views

In terms of complexity, is there a quicker way of checking if a matrix is nonsingular than computing the determinant?

To repeat the question, let $A$ be a square matrix. We wish to determine if $A$ is nonsingular, that is, invertible. One way is compute its determinant and check if it is nonzero. However, if $A$ is ...
4
votes
3answers
97 views

What would be complexity of computing $3^{n^n}$?

Just curious, what would be the computational complexity of computing $3^{n^n}$? I am not sure what it would be like.
0
votes
1answer
92 views

How can I do this kind of Cholesky decomposition?

$B_{(n+1)(n+1)}$ = $ \begin{bmatrix} A & u \\ u^T & 1 \\ \end{bmatrix}$ = $\begin{bmatrix} L_{11} & 0 \\ L_{21} & l_{22} \\ ...
0
votes
2answers
250 views

Inverse of matrix with QR method

What is the complexity of finding the inverse of matrix by QR decomposition? A is a $n×n$ with full rank.
2
votes
0answers
113 views

matrix construction

Given any matrix $A$, can one construct a matrix $B$ such that $B$ is nonnegative and the spectral radius of $B$ is strictly less than 1 the determinant of $A$ is equal to the first entry of $B^*$ ...
2
votes
1answer
174 views

Complexity of Gauss elimination over ring $Z_n.$

Is there some polynomial upper-bound for Gauss elimination over ring $Z_n$? I'm interested in polynomial bound depending from size of matrix and $\log n$. I also have the same question about the ...
2
votes
0answers
261 views

Proving that basic linear algebra problems (LINEQ and Linear Programming) are in NP

I'm working through the problems in Arora & Barak's textbook on Computational Complexity. It's all been good so far, but I'm kind of stuck on this pair of problems in Chapter 2 (2.3 and 2.4). I'm ...
6
votes
0answers
422 views

Hardness of finding eigenvalues over finite fields

How hard is it (computationally) to find eigenvalues/eigenvectors of matrices over finite fields? Suppose the field has size exponential in the input. (Does the QR algorithm still converge?) How ...
3
votes
2answers
404 views

equivalence between matrix multiplication and matrix inversion

I am a bit confused with this wikipedia article, hoping someone can clarify it. Looking at the Strassen algorithm page it is clear that this is an algorithm for reducing multiplication operations. ...
9
votes
2answers
644 views

Has there been a rigorous analysis of Strassen's algorithm?

According to Wikipedia, Strassen's Algorithm runs in $O(N^{2.807})$ time. Has anyone seen a more rigorous analysis displaying constants, possibly in a specific language such as C or Java? I ...
1
vote
1answer
862 views

Gauss Jordan elimination - count of steps for $N \times M$ equation

I am having some problem wrapping my head around an assignment. I have to find out how many additions, subtractions, multiplications and divisions are used while solving an $N \times M$ linear ...